Graph Genius: раскрытие секретов определения ключевых узлов

Сетевой анализ

Graph Genius: раскрытие секретов определения ключевых узлов

Откройте для себя ключевые показатели для определения важности узла на графике

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

В степени и вне степени

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

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

import networkx as nx
# Create a simple Digraph
G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5)])
nx.draw(G, with_labels = True, node_color='#00b4d9')
# Calculate in-degree and out-degree for each node
for node in G.nodes():
    print("Node", node, "In-degree:", G.in_degree(node), "Out-degree:", G.out_degree(node))

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

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

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

Количество ребер, присоединенных к узлу, называется его степенью центральности. Для расчета стандартизированной оценки каждая оценка делится на n-1, где n — количество узлов.

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

Центральность по промежуточности узла v – это сумма доли всех пар кратчайших путей, проходящих через v.

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

Центральность узла uявляется обратной величиной среднего кратчайшего расстояния до u в целом n-1 доступных узлов.

import networkx as nx
# Create a simple graph
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5)])
# Calculate degree centrality
degree_centrality = nx.degree_centrality(G)
print("Degree centrality:", degree_centrality)
# Calculate closeness centrality
closeness_centrality = nx.closeness_centrality(G)
print("Closeness centrality:", closeness_centrality)
# Calculate betweenness centrality
betweenness_centrality = nx.betweenness_centrality(G)
print("Betweenness centrality:", betweenness_centrality)

Случайные прогулки

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

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

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

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

import networkx as nx
import numpy as np

# Create a simple graph
G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 1)])
# Perform unweighted random walk

def unweighted_random_walk_importance(G, num_walks, walk_length):
    """
    Calculates the importance of each node in a graph using random walks.
    :param G: NetworkX graph.
    :param num_walks: Number of random walks to perform.
    :param walk_length: Length of each random walk.
    :return: A dictionary of importance scores for each node.
    """
    importance_scores = {node: 0 for node in G.nodes()}
    for _ in range(num_walks):
        current_node = np.random.choice(list(G.nodes()))
        for _ in range(walk_length):
            next_node = np.random.choice(list(G.neighbors(current_node)))
            importance_scores[next_node] += 1
            current_node = next_node
    for node in importance_scores:
        importance_scores[node] /= num_walks * walk_length
    return importance_scores

print("Random Walk Importance:", unweighted_random_walk_importance(G, 10, 5))
nx.draw(G, with_labels = True, node_color='#00b4d9', pos = pos)

Рейтинг страницы

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

import networkx as nx
# Create a simple graph
G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 1)])
# Calculate PageRank
pagerank = nx.pagerank(G)
pagerank = {k: round(v, 3) for k, v in pagerank.items()}
print("PageRank:", pagerank)
nx.draw(G, with_labels = True, node_color='#00b4d9', pos = pos)

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

PageRank: математически интересный способ ранжирования в Интернете!
PageRank 101: эволюция, математика и понимание ранжирования в поисковых системахmedium.com

Другие показатели

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

Центральность по Кацу – это мера центральности, обобщающая центральность собственного вектора. Он рассматривает не только непосредственных соседей узла, но и соседей соседей и так далее. Мера определяется как решение уравнения Ax = λx, где A — матрица смежности графа, x — собственный вектор, λ — собственное значение.

HITS (тематический поиск, вызванный гиперссылкой) – это показатель, который измеряет значимость веб-сайтов в сети гиперссылок. Алгоритм состоит из двух частей: авторитета и хаба. Авторитет веб-страницы рассчитывается путем сложения оценок хаба всех страниц, которые на нее ссылаются, тогда как хаб веб-страницы определяется путем сложения оценок авторитетности всех страниц, которые на нее ссылаются.

Заключение

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

Ссылки: