Как составлять, понимать и рассчитывать свойства графиков
Теория графов - это изучение графов, которые представляют собой математические структуры, используемые для моделирования парных отношений между объектами. Эти графы состоят из узлов (также называемых точками и вершинами), которые обычно представляют объект или человека, и ребер (также называемых линиями или связями), которые представляют отношения между узлами. Графики имеют множество применений в машинном обучении, поэтому в этом сообщении в блоге мы рассмотрим, как создавать графики, некоторые важные измерения графиков и способы их вычисления, а также способы выполнения этих вычислений с использованием пакета Python NetworkX.
Создание графика
Создать график с помощью пакета NetworkX не так уж сложно, просто убедитесь, что он импортирован вместе с matplotlib, чтобы вы могли его построить.
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_node('A')
nx.draw(G, with_labels=True)
plt.show()
И вот так у вас есть рисунок графика! Мы можем сделать эти графы более сложными, добавив к ним больше узлов и ребер.
G = nx.Graph()
G.add_edge('A','B')
nx.draw(G, with_labels=True)
plt.show()
Добавление ребер позволяет нам изучить отношения между узлами. Полный обзор пакета NetworkX можно найти здесь. Созданное здесь ребро является неориентированным, это означает, что отношения между узлами A и B равны. Что, если мы хотим создать направленную кромку? Мы можем сделать это с помощью функции DiGraph.
G = nx.DiGraph()
G.add_edge('A','B')
nx.draw(G, with_labels=True)
plt.show()
Результат выглядит как на графике выше, за исключением того, что теперь на ребре есть стрелка, которая показывает нам направление, в котором указывает край. Направленный край может представлять множество вещей в реальном мире, например влияние социальных сетей или распространение инфекционного заболевания.
Хотя на красивые картинки приятно смотреть, бывает сложно понять их, особенно если они имеют большое количество узлов и краев. К счастью, есть измерения, которые мы можем проводить с помощью графиков, которые могут дать нам ценную информацию. Давайте нарисуем более сложный график, чтобы лучше понять эти измерения.
G = nx.Graph()
G.add_edge('A','B')
G.add_edge('A','C')
G.add_edge('A','D')
G.add_edge('B','C')
G.add_edge('B','E')
G.add_edge('B','F')
G.add_edge('C','E')
G.add_edge('C','D')
G.add_edge('C','F')
G.add_edge('E','F')
G.add_edge('D','G')
G.add_edge('F','G')
G.add_edge('G','H')
G.add_edge('G','I')
G.add_edge('H','J')
G.add_edge('H','K')
G.add_edge('H','L')
G.add_edge('J','M')
G.add_edge('J','N')
G.add_edge('J','O')
G.add_edge('J','K')
G.add_edge('J','L')
G.add_edge('M','N')
G.add_edge('M','L')
G.add_edge('N','O')
G.add_edge('O','P')
G.add_edge('P','Q')
nx.draw(G, with_labels=True)
plt.show()
Измерения центральности
Измерения центральности дают нам информацию о том, насколько важны узлы в графе. В зависимости от того, где находится узел, сколько у него соединений и к каким другим узлам он подключен, они могут иметь широкий спектр влияний на граф. Здесь мы рассмотрим некоторые наиболее популярные измерения центральности и то, как они рассчитываются.
Степень центральности измеряет количество ребер, прикрепленных к узлу. Он используется для определения того, какие узлы наиболее связаны. В ориентированных графах степень центральности разбита на входящую для входящих ребер и исходящую для исходящих. Чтобы вычислить нормализованную степень центральности узла, вы просто складываете количество ребер, прикрепленных к узлу, и делите его на общее количество узлов минус один. Математически, если мы хотим найти степень центральности узла x, мы можем использовать уравнение
где N - количество узлов на графе, а a имеет значение либо 0, либо 1, в зависимости от того, являются ли узлы x и y разделяют край. Мы можем использовать следующий код, чтобы найти измерения степени центральности для каждого узла.
for node in G.nodes():
print(node, nx.degree_centrality(G)[node])
Это дает нам результат
Это показывает нам, что узел J имеет наибольшую степень центральности. Это легко проверить визуально как J, так как большинство ребер, соединенных с ним с помощью 6.
Центральность близости измеряет среднее расстояние от одного узла до любого другого узла. Чем центральнее узел, тем ближе он ко всем остальным узлам. Близость узла обычно обозначается в его нормализованной форме, которая задается уравнением.
Где N - количество узлов на графе, а d (y, x) - расстояние между вершинами x и y. . В теории графов расстояние - это количество ребер в кратчайшем пути. На больших графиках -1 становится крошечным, поэтому обычно его опускают. Используя код
for node in G.nodes():
print(node, nx.closeness_centrality(G, node))
мы видим этот узел H как центральность с наивысшей степенью близости, что означает, что он находится ближе всего к наибольшему количеству узлов, чем все остальные узлы.
Центральность по промежуточности: измеряет количество кратчайших путей, по которым находится узел. Эта центральность обычно используется для определения потока информации через граф. Чем выше число, тем больше информации проходит через него. Центральность промежуточности может быть вычислена с помощью уравнения
где знаменатель - это количество кратчайших путей между вершинами u и v, а числитель - это количество кратчайших путей между вершинами u и v, проходящие через вершину x. Обычно это измерение масштабируется и обычно выполняется путем деления значения на количество пар, не включающих x, в результате чего остается окончательное значение от 0 до 1. Значение делится на (N-1) (N-2) для ориентированных графов и (N-1) (N-2) / 2 для неориентированных графов. С кодом
for node in G.nodes():
print(node, nx.betweenness_centrality(G)[node])
мы видим, что узел G имеет наивысшую промежуточную центральность в нашем графе, что означает, что он лежит на кратчайших путях.
Центральность собственного вектора: измеряет относительное влияние узла в сети или насколько хорошо узел связан с другими узлами с высокой степенью связи. Это математическое измерение фразы Дело не в том, что вы знаете, а в том, что вы знаете.
Вычисление центральности собственного вектора немного (или намного) сложнее, чем центральность других векторов. Математически центральность собственного вектора вычисляется по уравнению
где 𝜆 - наибольшее вычисленное собственное значение, M (x) - набор соседей вершины x, y - соседняя вершина, а G - оцениваемый график. a принимает значение либо 0, либо 1 в зависимости от того, являются ли x и y соседями. Это выражение является решением уравнения для собственных векторов
В этом случае A - это матрица смежности, которая по сути подсчитывает количество соединений между узлами в матричной форме, 𝜆 - собственное значение, упомянутое выше, а x - собственный вектор. что мы решаем.
При работе с большими матрицами, чтобы избежать нахождения решений на основе собственных значений для многочленов большой степени, собственный вектор находится с помощью итерационного процесса. Это объяснит этот процесс более наглядно, давайте рассмотрим простой пример. Начнем с простого графика ниже.
Здесь у нас есть 4 узла A, B, C и D с ребрами между (A , B), (A, C), (A, D ) и (B, C). Матрица смежности выглядит как
где элементы выровнены как A, B, C и D как в направлении строк, так и столбцов. Числа в матрице представляют, сколько ребер соединяют каждый узел. Например, верхнее левое число - 0, потому что есть 0 ребер, соединяющих A с A. Поскольку наш график не является направленным, он делает так, чтобы наша матрица была симметричной.
Отсюда мы умножаем эту матрицу на наш начальный вектор, который является просто вектором единиц. Это дает нам результат
отсюда мы берем нормализованный вектор и вставляем его обратно в уравнение, заменяя им исходный вектор. Повторение этого процесса дает нам
Этот процесс продолжается до тех пор, пока собственный вектор не сходится к устойчивому решению. В этом примере окончательное решение
Теперь, когда мы понимаем, как происходит этот процесс, мы можем вычислить центральность собственных значений нашего исходного графа. Мы можем сделать это с помощью кода
for node in G.nodes():
print(node, nx.eigenvector_centrality(G, max_iter=1000)[node])
который показывает нам, что узел C имеет наибольшую центральность собственного вектора. Интересно отметить, что максимум все четыре измерения центральности выполняются на отдельных узлах.
Можно еще много узнать о графиках и измерениях центральности, и я надеюсь, что этот пост поможет вам начать свое приключение с графами.
