centrality

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

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

Синтаксис

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'})

Figure contains an axes. The axes contains an object of type graphplot.

Вычислите ранг страницы каждого веб-сайта с помощью 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');

Figure contains an axes. The axes contains an object of type graphplot.

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

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;

Figure contains an axes. The axes contains an object of type graphplot.

Скрипт 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')

Figure contains an axes. The axes with title Minnesota Road Network contains an object of type graphplot.

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

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

Figure contains an axes. The axes with title Closeness Centrality Scores - Unweighted contains an object of type graphplot.

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

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

Figure contains an axes. The axes with title Closeness Centrality Scores - Weighted contains an object of type graphplot.

Вычислите взвешенную музыку центрированности соотношения "между" к графику, чтобы определить дороги, чаще всего найденные на кратчайшем пути между двумя узлами. Нормируйте баллы центрированности с фактором (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')

Figure contains an axes. The axes with title Betweenness Centrality Scores - Weighted contains an object of type graphplot.

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

свернуть все

Введите график в виде любого graph или digraph объект. Используйте graph создать неориентированного графа или digraph создать ориентированного графа.

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

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

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

Опция

Тип графика

Описание

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

'degree'

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

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

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

  • '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. Чтобы изменить это, задайте вес ребра для использования с 'Cost' или 'Importance' пары "имя-значение".

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

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

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

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

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

Стоимость обхода ребра в виде разделенной запятой пары, состоящей из 'Cost' и вектор из положительного веса ребра. I-ый вес ребра задает стоимость, сопоставленную с пересечением ребра 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' и вектор из неотрицательного веса ребра. I-ый вес ребра задает важность ребра findedge(G,i). Вес ребра нуля эквивалентен удалению того ребра из графика.

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

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

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

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

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

Примечание

'Importance' только применяется к 'degree'outdegreeindegree, '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

Поддержка

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