Центральность по собственному вектору (8 видео)

Собственный вектор центральности (центральности мера)

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

Google PageRank и центральность Каца являются вариантами центральности собственных векторов.

Использование матрицы смежности для нахождения центральности собственного вектора

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

где это набор соседей и постоянная С небольшой перестановкой это можно переписать в векторной записи как уравнение собственного вектора

В общем, будет много разных собственных значений для которого существует ненулевое решение собственного вектора. Однако дополнительное требование, чтобы все элементы в собственном векторе были неотрицательными, подразумевает (по теореме Перрона-Фробениуса), что только наибольшее собственное значение приводит к желаемой мере центральности. компонент связанного собственного вектора тогда дает относительную центральную оценку вершины в сети. Собственный вектор определяется только с точностью до общего множителя, поэтому только отношения центральностей вершин хорошо определены. Чтобы определить абсолютную оценку, необходимо нормализовать собственный вектор, например, так, чтобы сумма по всем вершинам была равна 1 или общее число вершин n. Степенная итерация является одним из многих алгоритмов собственных значений, которые можно использовать для нахождения этого доминирующего собственного вектора. Кроме того, это может быть обобщено так, чтобы записи в A могли быть действительными числами, представляющими силы соединения, как в стохастической матрице.

Ниже приведен код для вычисления собственного вектора центральности графа и его различных узлов.

def eigenvector_centrality(G, max_iter = 100 , tol = 1.0e — 6 , nstart = None ,

«» «Вычислить центральность собственного вектора для графа G.

Центральность собственного вектора вычисляет центральность для узла на основе

центральность своих соседей. Центральность собственного вектора для узла `i`

/ mathbf = / лямбда / mathbf

где `A` — матрица смежности графа G с собственным значением` / lambda`.

В силу теоремы Перрона – Фробениуса, существует уникальная и положительная

решение, если `/ лямбда` является наибольшим собственным значением, связанным с

собственный вектор матрицы смежности `A` ([2] _).

max_iter: целое число, необязательно

Максимальное количество итераций в степенном методе.

tol: float, опционально

Погрешность, используемая для проверки сходимости в итерации метода мощности.

nstart: словарь, необязательно

Начальное значение итерации собственного вектора для каждого узла.

вес: нет или строка, необязательно

Если None, все веса ребер считаются равными.

В противном случае содержит имя атрибута ребра, используемого в качестве веса.

Словарь узлов с центральностью собственного вектора в качестве значения.

Расчет собственного вектора выполняется методом степенной итерации и имеет

нет гарантии сходимости. Итерация остановится после « max_iter«

итерации или допуск ошибки « number_of_nodes (G) * tol«

Для ориентированных графов это «левая» центральность собственного вектора, которая соответствует

к ребрам в графе. Для внешней центральности собственного вектора

сначала переверните граф с помощью « G.reverse () «.

from math import sqrt

if type (G) = = nx.MultiGraph or type (G) = = nx.MultiDiGraph:

raise nx.NetworkXException( «Not defined for multigraphs.» )

raise nx.NetworkXException( «Empty graph.» )

if nstart is None :

# выберите начальный вектор с записями 1 / len (G)

x = dict ([(n, 1.0 / len (G)) for n in G])

# нормализовать начальный вектор

s = 1.0 / sum (x.values())

# сделать до max_iter итераций

for i in range (max_iter):

x = dict .fromkeys(xlast, 0 )

# сделать умножение y ^ T = x ^ TA

x[nbr] + = xlast[n] * G[n][nbr].get(weight, 1 )

s = 1.0 / sqrt( sum (v * * 2 for v in x.values()))

# это никогда не должно быть ноль?

err = sum ([ abs (x[n] — xlast[n]) for n in x])

raise nx.NetworkXError( «» «Eigenvector_centrality ():

итерация мощности не смогла сходиться в итерациях% d. «% (i + 1))» «» )

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

>>> import networkx as nx

>>> G = nx.path_graph( 4 )

>>> print ([ ‘%s %0.2f’ % (node,centrality[node]) for node in centrality])

Вывод вышеуказанного кода:

[ ‘0 0.37’ , ‘1 0.60’ , ‘2 0.60’ , ‘3 0.37’ ]

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

Ссылки
Вы можете прочитать больше о том же на

Содержание

Анализ социальных сетей/Ключевые понятия
Содержание
Общие понятия
Сетевые метрики
Плотность
Коэффициент кластеризации
Degree
Близость — Closeness
Центральность (Близость к центру)
Групповые показатели центральности
Анализ сплоченных подгрупп
Мосты (Bridges)
Графическая аналитика — Введение и концепции центральности
📹 Видео

Видео:Собственные значения и собственные векторы матрицы (4)Скачать

Анализ социальных сетей/Ключевые понятия

Видео:Собственные векторы и собственные числа линейного оператораСкачать

Содержание

Общие понятия

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

Традиционно для обозначения отдельного элемента социальной сети используют понятие «узел», если речь идет об исследованиях прикладного математического характера, или «актор», если подразумевается социологические исследования. В целом узел и актор по сути представляет собой отдельного человека (в социальных сетях), выступающего субъектом связей с другими индивидами.

Сетевые метрики

Показатели, которые используются при анализе социальных сетей. См. Сетевые метрики — таблица

Плотность

Плотность – это отношение числа имеющихся рёбер графа к максимально возможному количеству рёбер данного графа. Плотность – распространённая метрика, она используется в первую очередь при сравнении графов одного размера, или при сравнении графа с самим собой во времени. Вычисляется она по формуле:

2 * L / (g * (g — 1 )) — где L — число связей, а g — число вершин в графе

Например, если в системе 924 участника и между ними установлены 2561 связь, то плотность равна

Для NetLogo в ситуации, когда есть участники и связи между ними, рассчитывается по формуле

Коэффициент кластеризации

Кластеризация – это локальная характеристика сети. Она характеризует степень взаимодействия между собой ближайших соседей данного узла. В большинстве сетей, если узел А соединен с узлом В, а узел В – с узлом С, то существует большая вероятность, что узел А соединен с узлом С (друзья наших друзей обычно также являются и нашими друзьями).

Коэффициент кластеризации данного узла есть вероятность того, что два ближайших соседа этого узла сами есть ближайшие соседи.

Коэффициент С соответствует отношению реального числа связей между его соседями и их потенциально возможного числа. Для узла i Ci = Ei/[ki(ki-1)/2], где Ei реальное число связей, ki – степень узла, а в знаменателе записано суммарное число потенциально возможных связей между непосредственными соседями узла i (при котором сеть или еѐ часть превращается в полный граф).

Коэффициент кластеризации может быть усреднен для любой части сети или для сети в целом, становясь ее интегральной характеристикой: C = 1/n ΣCi.

Усредненный коэффициент кластеризации для групп участников школьной сети. Если мы можем по какому либо принципу выделить группу участников, то мы можем определить коэффициент кластеризации в пределах данной группы. Для членов устойчивой группы — клики — коэффициент кластеризации = 1.

Коэффициент кластеризации – это метрика, которая является более эффективной, чем плотность, и её всё чаще используют в общественных науках. Коэффициент кластеризации – степень, определяющая насколько узлы стремятся к кластеризации. Например, в сети друзей это вероятность того, что 2 моих друга являются друзьями между собой. То есть это некоторая оценка фрагментированности сети. При высокой кластеризации можно ожидать, что вирус будет распространяться лишь в определенной подгруппе (кластере). При низкой кластеризации высока вероятность быстрого распространения вируса по всей сети

Локальный коэффициент кластеризации

Коэффициент локального объединения в кластеры (коэффициент кластеризации) является мерой того, насколько хорошо связанны связаны между собой соседи данного узла. Локальный коэффициент кластеризации рассчитывается как число связей межу соседями данного узла / возможное число связей между соседями.

turtle nw:clustering-coefficient — local clustering coefficient of the turtle.

Reports the local clustering coefficient of the turtle. The clustering coefficient of a node measures how connected its neighbors are. It is defined as the number of links between the node’s neighbors divided by the total number of possible links between its neighbors.

nw:clustering-coefficient takes the directedness of links into account. A directed link counts as a single link whereas an undirected link counts as two links (one going one-way, one going the other).

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

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

Если рассматривать ценность сети с педагогической точки зрения — как создание устойчивых связей между всеми акторами сети, то для отдельного участника число его связей с другими участниками / на возможное число связей.

Глобальный коэффициент кластеризации

Коэффициент кластеризации – это значения кластеризации для всех узлов графа. Когда коэффициент кластеризации высокий – это означает, что граф чрезвычайно плотно сгруппирован вокруг нескольких узлов; когда он низкий – это значит, что связи в графе относительно равномерно распространены среди всех узлов.

Вычисляется на основании того сколько треугольников сложено в сети от возможного количества треугольников. Например, на следующей картинке коэффициент кластеризации равен 1/3 — потому что там моглор бы быть 3 треугольника, а сложился только 1

The global clustering coefficient measures how much nodes tend to cluster together in the network in general. It is defined based on the types of triplets in the network. A triplet consists of a central node and two of its neighbors. If its neighbors are also connected, it’s a closed triplet. If its neighbors are not connected, it’s an open triplet. The global clustering coefficient is simply the number of closed triplets in a network divided by the total number of triplets. It can be calculated from the local clustering coefficient quite easily with the following code

transitivity(g, type=»local») order(transitivity(g, type=»local»))

Насколько узлам свойственно объединяться в кластеры

Усредненный коэффициент кластеризации — The average local clustering coefficient is another popular method for measuring the amount of clustering in the network as a whole. It may be calculated with

Biconnected component — компонента сильной связности

Возвращает список бикомпонентных кластеров в текущем сетевом контексте. Бикомпонента (a maximal biconnected subgraph)- часть сети, которая не может быть разъединена благодаря удалению только одного связующего узла (шарнира). Чтобы рассыпать граф необходимо удалить хотя бы 2 узла. Бикомпонента (Strongly connected component) — максимальный по включению вершин сильно связный подграф орграфа.

Reports the list of bicomponent clusters in the current network context. A bicomponent (also known as is a part of a network that cannot be disconnected by removing only one node (i.e. you need to remove at least two to disconnect it). The result is reported as a list of agentsets, in random order. Note that one turtle can be a member of more than one bicomponent at once.

В исследовании школьной сети с GoogleApps было выделено 2 заметных бикомпоненты:

В первой бикомпоненте более 280 узлов

Во второй бикомпоненте только 6 узлов и здесь проще читается основное правило сильной бикомпоненты — все узлы внутри бикомпоненты связаны более чем с одним узлом и нет узла, удаление которого привело бы к утрате связей между акторами сети.

Компонента слабой связности

Reports the list of «weakly» connected components in the current network context. A weakly connected component is simply a group of nodes where there is a path from each node to every other node. A «strongly» connected component would be one where there is a directed path from each node to every other. The extension does not support the identification of strongly connected components at the moment.

The result is reported as a list of agentsets, in random order. Note that one turtle cannot be a member of more than one weakly connected component at once.

Degree

Количество узлов, связанных с данным узлом — степень данного узла.

Близость — Closeness

Мера скорости передачи информации. Как долго будет происходить передача информации от данного узла к другим связанным узлам. Инверсия суммы кратчайших расстояний между каждым узлом и каждым другим узлом в сети. Близость показывает, насколько просто одному узлу связаться с другим узлом. Чем меньше узлов-посредников между текущем узлом и другими узлами, тем ниже показатель близости и выше степень близости. Если узел централен, то он может быстро взаимодействовать с другими узлами.

Центральность (Близость к центру)

Для анализа связей в социальной сети используют различные индивидуальные и групповые показатели, позволяющие оценить степень заметности и влияния акторов друг на друга. Собственно идея центральности вершин в графе, их значения появилась одной из первых в методологии анализа социальных сетей, и напрямую может быть увязана с первыми попытками Дж. Морено выявить самых популярных участников в группе («социометрических звезд»). Позднее эта мера заметности актора в сети стала называться центральностью.

Близость к центру или Степень центральности (Degree centrality) – показывает, кто является наиболее активным узлом в сети. Измеряется количеством связей с другими узлами в сети. Центральность показывает, насколько данный узел близок по отношению к другим узлам в сети. В соответствие с теорией сетей большое количество взаимодействий узла может не только изменить позицию узла в сети, но также и изменить позиции других узлов.

Престиж узла: входная степень узла (in-degree) — количество ребер графа, входящих в узел.
Влияние узла: выходная степень узла (out-degree) — количество ребер графа, исходящих из узла. Эта характеристика показывает, кто является наиболее активным в сети. Индивидуальный показатель близости к центру показывает, в какой степени узел связан остальными узлами, то есть насколько тесно он связан с группой.

Freeman L.C. Centrality in social networks: Conceptual clarification // Social Networks. 1979. Т. 1. № 3. С. 215–239.

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

Центральность по степени

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

Центральность по степени – это отношение количества связей определённого узла к общему количеству других узлов. В случае направленной сети существует две отдельных меры ЦС: входящая (indegree) и исходящая (outdegree). Входящая указывает число связей, направленных к узлу, а исходящая – число связей, направленных от узла. Если ЦС = 1, это указывает на то, что определённый узел связан со всеми остальными узлами сети, в то время как ЦС = 0 указывает на то, что узел изолирован. Так как многие интернет-сети являются направленными, есть определённый смысл в том, чтобы использовать входящую и исходящую центральность по степени. Высокая исходящая центральность по степени указывает на то, что узел является «властным»; это такой тип человека или сайта, который может быстро распространить информацию среди других людей. Высокая входящая центральность по степени указывает, что узел – «знаменитость»; это значит, что за таким типом человека или сайта будет следить много людей. Google.com имеет миллиарды внешних ссылок на другие сайты. Это – власть. YouTube.com имеет относительно немного ссылок на другие сайты, однако, много людей размещают ссылки на YouTube или встраивают его контент на собственные страницы. Это – известность.

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

Если позиция, занимаемая актором-мостом, отличается высокой степенью центральности (degree centrality), то есть он имеет больше прямых связей с акторами, чем другие, он может широко распространять свои коммуникативные темы в тех сплоченных подгруппах, к которым принадлежит, тем самым внося вклад в сближение структуры и состава полей знания соответствующих РКС (распределенная когнитивная система). Чем меньше таких акторов, чем центральнее их позиция, тем больший вклад в обеспечение конгруэнтности полей знания они способны внести. Если же актор-мост в большой мере промежуточно централен (betweenness centrality), то есть чаще других находится на пути от одного актора сети к другому, он может контролировать значительное число информационных потоков между сплоченными подгруппами, членом которых является, а следовательно, ограничивать разнообразие информации. Его ошибки, намеренная дезинформация или необычные, творческие коммуникативные практики способны порождать наиболее отклоняющиеся информационные вариации в полях знания РКС. В случае, когда относительное количество таких акторов и их коммуникаций велико, они усиленно раздражают друг друга и порождают множество отклонений-новаций, а сопряжение между подгруппами сети, по-видимому, усиливается. Если же акторы скорее склонны ограничивать проходящую информацию, то сопряжение, вероятнее всего, будет ослабевать.

Басов Н.В. Создание знания в сетевых коммуникативных структурах // Социологический журнал. 2014. № 1. С. 106–123.

Центральность по близости closeness-centrality

Центральность по близости выражает, насколько близко узел расположен к остальным узлам сети. По мнению Фримана, это мера эффективности, так как узел, который является наиболее близким к остальным узлам графа, лучше всех подвержен восприятию новой информации или вируса. Формально центральность по близости выражается как отношение числа других узлов графа к сумме расстояний между определённым узлом и всеми другими. Если БЦ = 1, это означает, что определённый узел связан со всеми другими узлами. Вероятно, что сайты СМИ, которые имеют блог-платформы, такие как Gizmodo.com и DailyKOS.com имеют очень высокий показатель БЦ. Они содержат ссылки на большое количество других сайтов, и многие другие сайты, в свою очередь, ссылаются на них.

Центральность по близости (Closeness centrality) является показателем того, насколько быстро распространяется информация в сети от одного участника к остальным, то есть насколько близок рассматриваемый участник ко всем остальным участникам сети.

Показатель «центральность по близости» (closeness centrality) демонстрирует, насколько легко достичь определенного узла в сети. Если говорить о футболе, то этот показатель позволяет судить, как этот игрок взаимодействует с командой.

Суть его состоит в том, чтобы оценить насколько близок (то есть включен в непосредственное взаимодействие) актор ко всем остальным участникам сети. Для того чтобы иметь высокую степень данного вида центральности, актор должен не просто обладать множеством связей. Важно, чтобы у его друзей и партнеров тоже их было достаточно. Это означает, что актор с высокой степенью центральности по близости через те связи, в которые он включен, получает возможность доступа к большому количеству других участников сети, распространяя свое влияние на них. Не случайно так называемые влиятельные распространители информации имеют высокую степень центральности по близости. Например, если актор знает всех субъектов сети, то степень его центральности будет равна единице

The closeness centrality of a turtle is defined as the inverse of the average of it’s distances to all other turtles. — Обратное среднему от расстояний до всех других черепах.

см. https://github.com/NetLogo/NW-Extension — Сетевое расширение NetLogo — и отдельный раздел о измерении центральности

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

Центральность по посредничеству betweenness-centrality

Центральность по посредничеству — вынесено в отдельную статью по причине значимости

Групповые показатели центральности

Групповые показатели центральности являются мерами изменчивости или неравенства индивидуальных показателей в графе и показывают насколько различаются акторы по степени индивидуальной центральности. В таком общем понимании групповые индексы по смыслу близки дисперсии (мере разброса). По причинам математического свойства наиболее популярны групповые индексы Фримана по степени, близости или посредничеству. Каждый из этих показателей равен сумме отклонений индивидуальных показателей от максимального наблюдаемого, отнесенной к теоретически возможному максимуму сумм отклонений. Знаменатель получают аналитически. Групповые индексы равны нулю в том случае, когда все индивидуальные показатели равны, и 100, если в графе доминирует одна вершина. В отличие от дисперсии, групповые индексы не зависят от размера графа.

Для группового показателя центральности по посредничеству = Sum (maxV — Vi)/ (((N — 1)* (N — 1) * (N — 2) ) / 2)

Групповая центральность по посредничеству в NetLogo. Групповая центральность по посредничеству позволяет сравнивать проекты совместной сетевой деятельности независимо от числа участников

Мера центральности по собственному вектору eigenvector-centrality

Центральность по собственному вектору (Eigenvector centrality) демонстрирует зависимость между центральностью участника и центральностями его друзей.

The Eigenvector centrality of a node can be thought of as the amount of influence a node has on a network. In practice, turtles that are connected to a lot of other turtles that are themselves well-connected (and so on) get a higher Eigenvector centrality score.

Черепаха, которая имеет много связей с теми, у кого тоже много связей, имеет высокую центральность по собственному вектору.

Мера центральности по собственному вектору (eigenvector centrality) еще более сложна для вычисления и возможна только с помощью специализированных компьютерных программ. Идея ее измерения основана на принципе «скажи мне, кто твой друг, и я скажу, кто ты». Здесь усилия направлены на то, чтобы найти центральных акторов (то есть с наименьшей удаленностью от других) в условиях глобальной или масштабной, сложной по структуре сети, имеющих множество подгрупп, и преодолеть ограничение моделей, более подходящих для анализа локальных сообществ и сетей.

page-rank

weighted-closeness-centrality

Анализ сплоченных подгрупп

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

Простейшим методом анализа сплоченных подгрупп является идентификация клик. В терминах теории графов это максимальный полный подграф, включающий не менее трех вершин. По определению, все вершины клики связаны между собой, и при добавлении любой другой вершины это свойство теряется. Следует иметь в виду, что в отечественной социальной психологии закрепилось определение клики как сплоченной асоциальной группировки. Понятие клики является чрезмерно строгим, а полученные подмножества акторов неустойчивы: удаление или случайное отсутствие одной связи разрушает клику. Чтобы ослабить это ограничение, были разработаны другие меры сплоченности подгрупп. Они основаны либо на понятии достижимости вершин в подграфе, либо на степени вершины (смежность с другими).

Клика порядка n (n-клика) определена как максимальный подграф, в котором наибольшее расстояние между вершинами не превышает заданной величины n. Основным недостатком этого подхода является то, что наикратчайшие пути между членами n-клики могут проходить через посредников, которые сами не принадлежат сплоченной подгруппе. Это обстоятельство может создавать трудности в интерпретации результатов. Скорректированное понятие называется кланом порядка n. Кланы получают исключением из найденных n-клик подгрупп с диметром (наибольшим из самых коротких расстояний между вершинами), превышающим заданное n. Алгоритм поиска клик и кланов заданного порядка обычно приводит к большим подгруппам.

maximal-cliques

Клика, которая не является подмножеством более крупной клики.

Как достать клику размером больше N ?

Очень показательная картинка, где в центре основная клика цветом 93.

biggest-maximal-cliques

Получено по команде

Далее мы удаляем всех остальных участников и показываем клики

Мосты (Bridges)

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

Видео:Теория сетей: 5. ЦентральностьСкачать

Графическая аналитика — Введение и концепции центральности

Дата публикации Aug 13, 2019

Появление социальных сетей, больших данных и электронной коммерции еще раз подчеркнуло важность анализа уникального типа структуры данных, которая отображает отношения между ее сущностями, также известными как График. Необходимо кратко представить концепцию «Графа», прежде чем я решусь на введение в Graph Analytics.

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

Приведенное выше изображение изображает граф друзей, где узел / сущность, такая как A, B и т. Д., Изображает конкретного человека, а связь (также известная как ребро) между любыми двумя людьми изображает отношение («дружба» в данном случае) между их.

Обобщая из приведенного выше примера:

Графы могут быть определены как представление отношений между «сущностями» или «вещами», где эти «сущности» являются «узлами» (также известными как «вершины») графа, а отношения между ними представлены «связями» (также известный как «ребра») графа. Изучение графов также известно как «Теория графов»

Кроме того, просто взглянув на график, можно проанализировать, что у A и B есть общий друг C, который не дружит с D. Отрасль данных, занимающаяся извлечением информации из графиков путем выполнения анализа на них, известна как«Графическая аналитика».

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

центральность

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

Степень Центральности

Первый аромат Центральности, который мы собираемся обсудить, это «Степень Центральности«Чтобы понять это, давайте сначала рассмотрим концепциюстепеньузла в графе.

Внеориентированный графСтепень узла определяется как количество прямых соединений, которые узел имеет с другими узлами. Глядя на график ниже:

Вориентированный граф(у каждого ребра есть направление), степень узла далее делится на In-градус и Out-градус. Степень относится к числу ребер / соединений, падающих на него, а степень выхода относится к числу ребер / соединений от него к другим узлам. Давайте рассмотрим примерный график Twitter ниже, где узлы являются отдельными лицами, а ребра со стрелками указывают Отношения «следует»:

Мы можем видеть, что узлы E, C, D и B имеют исходящий край к узлу A и, следовательно, следуют за узлом A. Таким образом, степень узла A равна 4, так как у него есть 4 ребра, падающие на него.

Мы также можем видеть, что узел B следует как за узлом D, так и за узлом A, следовательно, его степень выхода равна 2.

Теперь показатель степени центральности определяет важность узла в графе как измеряемый на основе его степени, т. Е. Чем выше степень узла, тем важнее он в графе.

Пересматривая вышеупомянутый график друзей (рисунок 1) ниже:

Центральность степени узла A — 7, узла G — 5, узла C — 4, а узла L — 1.

Математически Степень Центральности определяется как D (i) для узла «i», как показано ниже:

Теперь давайте кратко обсудим пример приложения центральности степени к приведенному выше графику друзей. Глядя на узлы A и G, они имеют высокую степень централизации (7 и 5 соответственно) и будут идеальными кандидатами, если мы хотим быстро распространить любую информацию на большую часть сети по сравнению с узлом L, который имеет только степень централизации из 1.Эта информация очень полезна для создания маркетинговой или влияющей стратегии, если в сети необходимо внедрить новый продукт или идею / идею. Маркетологи могут сосредоточиться на таких узлах, как A, G и т. Д. С высокой степенью централизации, чтобы продавать свой продукт или идеи в сети, чтобы обеспечить более высокую доступность среди узлов

Точно так же, имея в виду примерный график Twitter (на рисунке 2), если мы на самом деле исследуем социальную сеть, такую как Twitter, с миллионами узлов и вычисляем центральную степень для различных узлов, то узлы с высокой степенью центральности (такие как Канье Уэст, Леди Гага и другие знаменитости будут узлами, которые имеют огромное количество подписчиков и могут стать идеальными кандидатами для влияния на публику или продвижения коммерческих продуктов. Теперь вы знаете, почему знаменитостям или популярным людям платят в социальных сетях, таких как Instagram и Twitter, за то, что они говорят определенные вещи или продвигают определенные продукты, поскольку коммерческие компании знают, что эти люди имеют очень высокую степень и способны влиять или достигать большое количество людей быстро.

Применение / Полезность анализа важности узлов на основе степени централизации огромна и зависит от рассматриваемой природы графа / сети.

Центральность

Второй аспект, который мы собираемся обсудить, — это «Центральность близости». Чтобы понять то же самое, сначала давайте поймем концепцию «Геодезическая дистанция »между двумя узлами в графе.

Геодезическое расстояние d между двумя узлами а такжебопределяется как число ребер / связей между этими двумя узлами на кратчайшем пути (путь с минимальным количеством ребер) между ними.

Давайте посмотрим на график ниже:

Давайте рассмотрим геодезическое расстояние между A и F для дальнейшего уточнения концепции. Мы можем достичь F из A, пройдя через B и E или пройдя через D. Однако кратчайший путь из F в A проходит через D (2 ребра), поэтому геодезическое расстояние d (A, F) будет определено как 2 так как есть 2 ребра между А и F.

Математически геодезическое расстояние можно определить следующим образом:

д ( ,б)= Количество ребер между а такжебна кратчайшем пути из вбесли путь существует из вб

д ( ,б)= 0, если а =б

д ( ,б)= ∞ (бесконечность), если путь не существует из вб

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

Опять же, взглянув на ранее представленный граф друзей на рисунке 1 ниже, мы видим, что центральность узла A равна 17, а центральности узла L — 33.

Математически, Центральность C (i) узлаяна графике можно определить, как показано ниже:

Давайте кратко опишем пример приложения Closeness Centrality, изучив граф друзей выше на рисунке 5. Теперь давайте предположим, что в графе друга каждая ссылка / ребро имеет вес (атрибут), равный 1 минуте, т.е. это займет 1 минуту. для передачи информации от узла к соседнему узлу, такому как от A до B или от B до C. Теперь давайте предположим, что мы хотим отправить фрагмент конкретной информации (информация будет отличаться для каждого узла) каждому узлу графа, и нам нужно выбрать узел на графике, который может быстро передать его всем узлам сети.

Чтобы решить вышеупомянутую проблему, мы можем вычислить меру Центральности близости для всех узлов в сети. Как мы уже рассчитывали выше для узла A, если мы выберем узел A, информация может достигнуть всех узлов, пройдя 17 ребер (т.е. начиная с A, информация может быть передана на все узлы за 17 минут в худшем случае, при условии последовательной отправки из А) по сравнению с узлом L, где для передачи информации всем узлам потребуется 33 минуты. Очевидно, мы можем видеть разницу в важности обоих узлов A и L с точки зрения измерения центральности близости.

Центральность между

Третий аспект центральности, который мы собираемся обсудить, известен как «Центральность между» (BC). Эта метрика определяет и измеряет важность узла в сети на основе того, сколько раз он встречается на кратчайшем пути между всеми парами узлов в графе. Для дальнейшей разработки метрики давайте еще раз посмотрим на график наших друзей ниже:

Математически, Межцентричность Центральности B (i) узлаяна графике определяется следующим образом:

Глядя на узел A, можно заметить, что он лежит на кратчайшем пути между следующей парой узлов: (D, M), (D, E), (G, C), (G, B), (G, F ), (G, I), (K, C), (D, C) и т. Д. И, таким образом, имеет самый высокий BC среди всех других узлов графа. Мы также можем заметить, что оба узла G и C также имеют высокие межцентровые центральности (BC) по сравнению с другими узлами (кроме A) в графе.

Как уже говорилось, если мы посмотрим на график наших друзей выше (рисунок 6), узел A имеет очень высокий BC Если бы мы удалили его, это привело бы к огромному нарушению работы сети, поскольку у узлов не было бы возможности связаться с узлами и наоборот, и в итоге мы получили бы два изолированных подграфа. Это понимание отмечает важность узлов с высоким BC.

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

Реальный пример использования вышеуказанного приложения заключается в анализе глобальных террористических сетей. Например, если у нас есть сеть террористов или террористических групп и других связанных лиц, представленных в виде узлов графа, мы можем рассчитать BC для каждого узла и идентифицировать узлы с высоким BC. Эти узлы (или террористы в этом случае) будут мостовыми узлами в сети. Эта информация очень полезна для оборонных ведомств, поскольку они могут быть очень эффективными в подрыве всей террористической сети. Другой вариант использования этой метрики — обнаружение и мониторинг возможных узких мест или горячих точек в компьютерных сетях или потоковых сетях.

Собственный вектор центральности

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

Давайте посмотрим на график, приведенный ниже, для дальнейшего объяснения концепции:

Матрица смежности приведенного выше графика будет как показано ниже:

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

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

Теперь математически центральность собственного вектора вычисляется следующим образом:

Результирующий 1-D вектор в вышеприведенном уравнении дает оценку центральности собственного вектора (EVC) для каждого из узлов на графике. Эффект первой итерации умножения можно визуализировать, как показано ниже:

Как вы можете видеть выше, оба узла A и B имеют высокий балл 8, так как оба они подключены к множеству узлов с высокой степенью (важности), в то время как узел E имеет 3 балла, поскольку он подключен только к одному узлу степени 3. Также важно отметить, что значение оценки EVC для каждого узла в результирующем векторе является ничем иным, как суммой степеней соседних узлов. Например: оценка EVC для узла A = степень (B) + степень (C) + степень (D) = 8

Теперь, если результирующий вектор EVC, который мы получили выше в уравнении (рисунок 11), снова умножается на матрицу смежности A, мы получим большие значения для оценки EVC для каждого узла в графике, как показано ниже:

Эффект умножения результирующего вектора снова (2-я итерация умножения) с матрицей смежности может быть визуализирован, как показано ниже:

Теперь, почему мы снова умножили результирующий вектор на матрицу смежности?

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

Развивая вышеизложенное, если мы визуализируем вышеуказанные операции, мы можем наблюдать следующее:

После первой итерации умножения каждый узел получает оценку EVC от своих прямых (1-й степени) соседей.
Во второй итерации, когда мы снова умножаем результирующий вектор на матрицу смежности, каждый узел снова получает свою оценку EVC от своих прямых соседей, но разница во второй итерации заключается в том, что на этот раз на оценки прямых соседей уже оказали влияние ранее их собственными прямыми (1-й степени) соседями (из первой итерации умножения), что в конечном итоге помогает счету EVC любого узла также быть функцией соседних с ним узлов 2-й степени.
На последующих итерациях умножения оценка EVC узлов графа постоянно обновляется, поскольку на нее влияют оценки EVC от соседних узлов более высокой степени (3-й, 4-й и т. Д.).

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

Обсуждение приложений Eigen Vector Centrality обширно и заслуживает отдельной статьи. Одним из примеров применения EVC является вычисление алгоритма Page Rank или Page Rank, используемого Google и многими другими компаниями для ранжирования веб-страниц в Интернете по релевантности. Page Rank — это прямой вариант EVC. Веб-страницы в World Wide Web имеют ссылки, которые указывают на / с других веб-страниц. Вы можете думать о том, что каждая веб-страница является узлом на графике, а каждая исходящая / входящая ссылка — направленным ребром, ведущим на другую веб-страницу в сети или с нее, что составляет весь граф Всемирной паутины. График веб-страниц во всемирной паутине подвергается нескольким итерациям расчета EVS, чтобы рассчитать глобально точные рейтинги релевантности каждой веб-страницы. Затем веб-страницы с высокими показателями EVC могут быть предназначены для маркетинга и других коммерческих целей.

Область графовой аналитики обширна и имеет огромное практическое применение. Цель этой статьи — охватить основы центральности и, надеюсь, даст читателю представление об увлекательном мире графической аналитики.

Ниже приведен список различных библиотек и программного обеспечения Graph Analytics, которые можно использовать для Graph Analytics: