центрированность

Измерьте важность узла

свернуть все на странице

Синтаксис

C = centrality(G,type)
C = centrality(___,Name,Value)

Описание

пример

C = centrality(G,type) вычисляет центрированность узла, заданную type для каждого узла в графике.

пример

C = centrality(___,Name,Value) дополнительные опции использования заданы одним или несколькими Аргументами пары "имя-значение". Например, centrality(G,'closeness','Cost',c) задает стоимость пересечения каждого ребра.

Примеры

свернуть все

Скрипт Open Live Script

Создайте и постройте график, содержащий шесть фиктивных веб-сайтов.

s = [1 1 2 2 3 3 3 4 5];
t = [2 5 3 4 4 5 6 1 1];
names = {'http://www.example.com/alpha', 'http://www.example.com/beta', ...
         'http://www.example.com/gamma', 'http://www.example.com/delta', ...
         'http://www.example.com/epsilon', 'http://www.example.com/zeta'};
G = digraph(s,t,[],names);
plot(G,'NodeLabel',{'alpha','beta','gamma','delta','epsilon','zeta'})

Вычислите ранг страницы каждого веб-сайта с помощью функции centrality. Добавьте эту информацию к таблице Nodes графика как атрибут вершин графика.

pg_ranks = centrality(G,'pagerank')
pg_ranks = 6×1

    0.3210
    0.1706
    0.1066
    0.1368
    0.2008
    0.0643


G.Nodes.PageRank = pg_ranks;
G.Nodes
ans=6×2 table
                  Name                  PageRank
    ________________________________    ________

    'http://www.example.com/alpha'      0.32098 
    'http://www.example.com/beta'       0.17057 
    'http://www.example.com/gamma'      0.10657 
    'http://www.example.com/delta'      0.13678 
    'http://www.example.com/epsilon'    0.20078 
    'http://www.example.com/zeta'       0.06432

Также определите, какие узлы являются концентраторами и полномочиями с помощью centrality и добавляют очки к таблице Nodes.

hub_ranks = centrality(G,'hubs');
auth_ranks = centrality(G,'authorities');
G.Nodes.Hubs = hub_ranks;
G.Nodes.Authorities = auth_ranks;
G.Nodes
ans=6×4 table
                  Name                  PageRank       Hubs       Authorities
    ________________________________    ________    __________    ___________

    'http://www.example.com/alpha'      0.32098        0.24995    7.3237e-05 
    'http://www.example.com/beta'       0.17057        0.24995      0.099993 
    'http://www.example.com/gamma'      0.10657        0.49991      0.099993 
    'http://www.example.com/delta'      0.13678     9.1536e-05       0.29998 
    'http://www.example.com/epsilon'    0.20078     9.1536e-05       0.29998 
    'http://www.example.com/zeta'       0.06432              0       0.19999
Скрипт Open Live Script

Создайте и постройте взвешенный график с помощью случайной разреженной матрицы смежности. С тех пор существует много ребер, использует очень маленькое значение для EdgeAlpha, чтобы сделать ребра в основном прозрачными.

A = sprand(1000,1000,0.15);
A = A + A';
G = graph(A,'omitselfloops');
p = plot(G,'Layout','force','EdgeAlpha',0.005,'NodeColor','r');

Вычислите центрированность степени каждого узла. Задайте важность каждого ребра с помощью веса ребра.

deg_ranks = centrality(G,'degree','Importance',G.Edges.Weight);

Используйте discretize, чтобы поместить узлы в 7 равномерно распределенных интервалов на основе их очков центрированности.

edges = linspace(min(deg_ranks),max(deg_ranks),7);
bins = discretize(deg_ranks,edges);

Сделайте размер каждого узла в графике пропорциональным его счету центрированности. Размер маркера каждого узла равен интервалу номер (1-7).

p.MarkerSize = bins;

Скрипт Open Live Script

Загрузите данные в minnesota.mat, который содержит объект диаграмм G, представляющий сеть дорог в Миннесоте. Вершинам графика содержали координаты xy в переменных XCoord и YCoord таблицы G.Nodes. 

load minnesota.mat
xy = [G.Nodes.XCoord G.Nodes.YCoord];

Добавьте вес ребра в график, который примерно соответствует длине дорог, вычисленное использование Евклидова расстояния между координатами xy конечных узлов каждого ребра.

[s,t] = findedge(G);
G.Edges.Weight = hypot(xy(s,1)-xy(t,1), xy(s,2)-xy(t,2));

Постройте график с помощью координат xy для узлов.

p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'MarkerSize',5);
title('Minnesota Road Network')

Вычислите центрированность близости каждого узла. Масштабируйте цвет узла NodeCData, чтобы быть пропорциональными счету центрированности.

ucc = centrality(G,'closeness');
p.NodeCData = ucc;
colormap jet
colorbar
title('Closeness Centrality Scores - Unweighted')

Также вычислите взвешенный счет центрированности близости, с помощью веса ребра в качестве стоимости пересечения каждого ребра. Используя дорожные длины как вес ребра улучшает качество счета, поскольку расстояния теперь измеряются как сумма длин всех перемещенных ребер, а не количество ребер переместилось.

wcc = centrality(G,'closeness','Cost',G.Edges.Weight);
p.NodeCData = wcc;
title('Closeness Centrality Scores - Weighted')

Вычислите взвешенную музыку центрированности соотношения "между" к графику, чтобы определить дороги, чаще всего найденные на кратчайшем пути между двумя узлами. Нормируйте очки центрированности с фактором (n-2)(n-1)2 так, чтобы счет представлял вероятность, что путешественник вдоль кратчайшего пути между двумя случайными узлами переместится через данный узел. График показывает, что существует несколько очень важных введений дорог и из города.

wbc = centrality(G,'betweenness','Cost',G.Edges.Weight);
n = numnodes(G);
p.NodeCData = 2*wbc./((n-2)*(n-1));
colormap(flip(autumn,1));
title('Betweenness Centrality Scores - Weighted')

Входные параметры

свернуть все

Входной график, заданный как объект граф или диграф. Используйте граф для создания неориентированного графа или диграф для создания ориентированного графа.

Пример: G = graph(1,2)

Пример: G = digraph([1 2],[2 3])

Тип центрированности узла, заданной как одна из опций в таблице. Таблица также приводит совместимые Пары "имя-значение", которые работают с каждым типом. Каждое разнообразие центрированности узла предлагает различную меру важности узла в графике.

Опция

Тип графика

Описание

Пары "имя-значение"

'degree'

Неориентированный

'degree', 'outdegree' и типы центрированности 'indegree' основаны на количестве ребер, соединяющихся с каждым узлом:

  • градус Количество ребер, соединяющихся с каждым узлом. Самоцикл рассчитывает как два ребра, соединяющиеся с узлом.

  • indegree Количество входящих ребер к каждому узлу. Самоцикл рассчитывает как одно входящее ребро.

  • outdegree Количество исходящих ребер от каждого узла. Самоцикл рассчитывает как одно исходящее ребро.

Если вы задаете вес ребра 'Importance', то алгоритм использует сумму веса ребра, а не количество соединяющихся ребер.

'Importance'

'indegree'

'outdegree'

Направленный

'closeness'

Неориентированный

'closeness', 'incloseness' и типы центрированности 'outcloseness' используют обратную сумму расстояния от узла до всех других узлов в графике. Если не все узлы достижимы, то центрированность узла i:

c(i)=(A iN−1)21Ci .

A i - количество достижимых узлов от узла i (не считающий i), N, является количеством узлов в G и C, i - сумма расстояний от узла i ко всем достижимым узлам.

  • Если никакие узлы не достижимы от узла i, то c(i) является нулем.

  • Для 'incloseness' мерой по расстоянию является от всех узлов до узла i.

  • Вес ребра 'Cost' задает длину ребер.

'Cost'

'incloseness'

'outcloseness'

Направленный

'betweenness'

Неориентированный или направленный

Центрированность 'betweenness' вводит меры, как часто каждая вершина графика появляется на кратчайшем пути между двумя узлами в графике. С тех пор может быть несколько кратчайших путей между двумя вершинами графика s и t, центрированность узла, который u:

c(u)=∑s,t≠unst(u)Nst .

nst(u) количество кратчайших путей от s до t, которые проходят через узел u, и Nst общее количество кратчайших путей от s до t.

  • Если график является неориентированным, то пути от s до t и от t до s рассчитывают только как один путь (разделите формулу на два).

  • Вес ребра 'Cost' указывает, что длина ребер и справки определяет кратчайшие пути между узлами s и t.

'Cost'

'pagerank'

Неориентированный или направленный

Тип центрированности 'pagerank' следует из случайного обхода сети. В каждом узле в графике следующий узел выбран с вероятностью 'FollowProbability' от группы преемников текущего узла (соседи к неориентированному случаю). В противном случае, или когда узел не имеет никаких преемников, следующий узел выбран из всех узлов. Счет центрированности является средним временем, проведенным в каждом узле во время случайного обхода.

  • Если узел имеет самоцикл, то существует шанс, что алгоритм пересекает его. Поэтому самоциклы увеличивают счет центрированности PageRank узла, к которому они присоединяют.

  • В мультиграфах с несколькими ребрами между теми же двумя узлами более вероятно, будут выбраны узлы с несколькими ребрами.

  • Вес ребра 'Importance' влияет, как алгоритм выбирает преемников. Узлы с более высокой важностью, более вероятно, будут выбраны.

'Importance'

'FollowProbability'

'Tolerance'

'MaxIterations'

'eigenvector'

Неориентированный

Тип центрированности 'eigenvector' использует собственный вектор, соответствующий самому большому собственному значению матрицы смежности графика. Очки нормированы таким образом, что сумма всех очков центрированности равняется 1.

  • Если существует несколько разъединенных компонентов, то алгоритм вычисляет центрированность собственного вектора индивидуально для каждого компонента, то шкалы очки согласно проценту вершин графика в том компоненте.

  • Счетом центрированности разъединенных узлов является 1/numnodes(G).

  • Задайте вес ребра 'Importance', чтобы использовать взвешенную матрицу смежности в вычислении.

'Importance'

'Tolerance'

'MaxIterations'

'hubs'

'authorities'

Направленный

'hubs' и очки центрированности 'authorities' являются двумя соединенными мерами по центрированности, которые являются рекурсивными. Счет концентраторов узла является суммой множества полномочий всех ее преемников. Точно так же счет полномочий является суммой множества концентраторов всех ее предшественников. Сумма всех очков концентраторов равняется 1, и сумма всех очков полномочий равняется 1.

  • Эти очки могут быть интерпретированы как левое (концентраторы) и право (полномочия) сингулярные векторы, соответствующие самому большому сингулярному значению матрицы смежности.

  • Счетом центрированности разъединенных узлов является 1/numnodes(G).

  • Задайте вес ребра 'Importance', чтобы использовать взвешенную сумму, а не простую сумму всех очков преемника/предшественника. Это эквивалентно использованию сингулярных векторов взвешенной матрицы смежности.

  • Если существует несколько разъединенных компонентов (в слабо связанном смысле), то алгоритм вычисляет концентраторы и музыку полномочий индивидуально к каждому компоненту. Очки затем повторно масштабируются согласно проценту вершин графика в том компоненте так, чтобы полная сумма равнялась все еще 1.

'Importance'

'Tolerance'

'MaxIterations'

Примечание

Функция centrality принимает, что весь вес ребра равен 1. Чтобы изменить это, задайте вес ребра для использования с парами "имя-значение" 'Importance' или 'Cost'.

Пример: centrality(G,'degree')

Пример: centrality(G,'hubs','Tolerance',tol)

Аргументы в виде пар имя-значение

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (Name) — это имя аргумента, а значение (Value) — соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: C = centrality(G,'closeness','Cost',edgeCosts) вычисляет центрированность близости с помощью edgeCosts в качестве стоимости (вес) пересечения каждого ребра в графике.

Стоимость обхода ребра, заданного как пара, разделенная запятой, состоящая из 'Cost' и вектор положительного веса ребра. ith вес ребра задает стоимость, сопоставленную с пересечением ребра findedge(G,i). Весь вес ребра должен быть больше, чем нуль.

Вес ребра 'Cost' меньше, когда связь является короче, или быстрее или более дешевой. Некоторые примеры веса ребра 'Cost':

  • Длина пути

  • Время прохождения

  • Стоимость билета

Примечание

'Cost' только применяется к 'closeness', 'outcloseness', 'incloseness' и типам центрированности 'betweenness'.

Пример: centrality(G,'closeness','Cost',c)

Вероятность выбора узла преемника, заданного как пара, разделенная запятой, состоящая из 'FollowProbability' и скаляра между 0 и 1. Следовать вероятность является вероятностью, что следующий узел, выбранный в обходе алгоритмом PageRank, выбран среди преемников текущего узла, и не наугад от всех узлов. Для веб-сайтов эта вероятность соответствует щелчку по ссылке на текущей веб-странице вместо того, чтобы переместиться к другой случайной веб-странице.

Примечание

'FollowProbability' только применяется к типу центрированности 'pagerank'.

Пример: centrality(G,'pagerank','FollowProbability',0.5)

Важность ребра, заданная как пара, разделенная запятой, состоящая из 'Importance' и вектор неотрицательного веса ребра. ith вес ребра задает важность ребра findedge(G,i). Вес ребра нуля эквивалентен удалению того ребра из графика.

Для мультиграфов с несколькими ребрами между двумя узлами centrality добавляет несколько ребер вместе и обрабатывает их как одно ребро с объединенным весом.

Вес ребра 'Importance' больше, когда связь более сильна. Некоторые примеры веса ребра 'Importance':

  • Количество путешественников в день

  • Количество нажимает на ссылку

  • Количество бумаг опубликовано вместе

Примечание

'Importance' только применяется к 'degree', 'outdegree', 'indegree', 'pagerank', 'eigenvector', 'hubs' и типам центрированности 'authorities'.

Пример: centrality(G,'degree','Importance',x)

Максимальное количество итераций, заданных как пара, разделенная запятой, состоящая из 'MaxIterations' и скаляра. Выполнениям алгоритма centrality до допуска соответствуют, или максимальное количество итераций достигнуто, какой бы ни на первом месте.

Примечание

'MaxIterations' только применяется к 'pagerank', 'eigenvector', 'hubs' и типам центрированности 'authorities'.

Пример: centrality(G,'pagerank','MaxIterations',250)

Остановка критерия итеративных решателей, заданных как пара, разделенная запятой, состоящая из 'Tolerance' и скаляра. Выполнениям алгоритма centrality до допуска соответствуют, или максимальное количество итераций достигнуто, какой бы ни на первом месте.

Примечание

'Tolerance' только применяется к 'pagerank', 'eigenvector', 'hubs' и типам центрированности 'authorities'.

Пример: centrality(G,'pagerank','Tolerance',1e-5)

Выходные аргументы

свернуть все

Очки центрированности узла, возвращенные как вектор-столбец. C(i) является счетом центрированности узла i. Интерпретация счета центрированности узла зависит от типа выбранного вычисления центрированности. Чем более центральный узел, тем больше его счет центрированности.

Смотрите также

|

Введенный в R2016a

Документация MATLAB
Поддержка
Для просмотра документации необходимо авторизоваться на сайте