Чтобы вычислить посредничество вершины a в определенном aGraph = ( , ), выполните следующие действия:

1.Вычислите кратчайший путь между каждой парой вершин в aGraph. Давай­ те представим это с помощью .

Удаленность и близость

Представим себе граф g. Удаленность (fairness) вершины a в графе g определя­ ется как сумма расстояний от вершины a до других вершин. Обратите внимание, что центральность конкретной вершины количественно определяет ее общее расстояние от всех остальных вершин.

Противоположностью удаленности выступает близость (closeness).

Влиятельность

Влиятельность, или центральность собственного вектора (Eigenvector centra­ lity), оценивает все вершины графа, определяя их важность в сети. Эта оценка — показатель связи конкретной вершины с другими важными вершинами во всей сети. Когда в Google создавали алгоритм PageRank, который присваивает оцен­ ку каждой веб-странице в интернете (чтобы отразить ее важность), идею они взяли из показателя влиятельности.

Вычисление показателей центральности с помощью Python

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

import networkx as nx

import matplotlib.pyplot as plt vertices = range(1,10)

edges = [(7,2), (2,3), (7,4), (4,5), (7,3), (7,5), (1,6),(1,7),(2,8),(2,9)] G = nx.Graph()

G.add_nodes_from(vertices)

G.add_edges_from(edges)

nx.draw(G, with_labels=True,node_color='y',node_size=800)