中心性算法

此 Jupyter Notebook 托管在 Neo4j 图数据科学客户端 Github 仓库的此处。

中心性算法用于理解图中特定节点的角色或影响力。本 Notebook 展示了如何使用 graphdatascience 库在此处可下载的航空公司旅行可达性网络数据集上应用中心性算法。

本 Notebook 将展示如何对图数据集应用特征向量中心性、介数中心性、度中心性和紧密中心性。

1. 设置

我们首先导入依赖项并设置与数据库的 GDS 客户端连接。

或者，您可以使用Aura 图分析无服务器并跳过下面的整个设置部分。

# Install necessary dependencies
%pip install graphdatascience pandas

import os

import pandas as pd

from graphdatascience import GraphDataScience

NEO4J_URI = os.environ.get("NEO4J_URI", "bolt://localhost:7687")
NEO4J_AUTH = None
if os.environ.get("NEO4J_USER") and os.environ.get("NEO4J_PASSWORD"):
    NEO4J_AUTH = (
        os.environ.get("NEO4J_USER"),
        os.environ.get("NEO4J_PASSWORD"),
    )

gds = GraphDataScience(NEO4J_URI, auth=NEO4J_AUTH)

from graphdatascience import ServerVersion

assert gds.server_version() >= ServerVersion(1, 8, 0)

2. 导入数据集

我们首先将数据集导入为 pandas 数据帧。这里处理两个文件。文件 reachability-meta.csv.gz 存储城市名称及其信息，而文件 reachability.txt.gz 存储图的边。如果估计的航空旅行时间小于某个阈值，则从城市 i 到城市 j 存在一条边。

nodes_info_df = pd.read_csv("https://snap.stanford.edu/data/reachability-meta.csv.gz", compression="gzip")
nodes_info_df.head()

routes_df = pd.read_csv(
    "https://snap.stanford.edu/data/reachability.txt.gz",
    sep=" ",
    skiprows=6,
    header=None,
    compression="gzip",
    names=["Origin", "Destination", "Weight"],
)
routes_df.head()

由于此图非常小，因此使用直接的 Cypher UNWIND 查询是在数据库中创建图的最简单方法。

更大的图可能需要更复杂的导入技术，例如批处理、neo4j-admin import 或 Arrow CREATE DATABASE。

gds.run_cypher(
    "UNWIND $nodes AS node CREATE (n:City {node_id: node.node_id, name: node.name, population: node.metro_pop})",
    params={"nodes": nodes_info_df.to_dict("records")},
)

gds.run_cypher(
    """
    UNWIND $rels AS rel
    MATCH (source:City {node_id: rel.Origin}), (target:City {node_id: rel.Destination})
    CREATE (source)-[:HAS_FLIGHT_TO]->(target)
    """,
    params={"rels": routes_df.to_dict("records")},
)

G, result = gds.graph.project("airline", "City", "HAS_FLIGHT_TO")

print(f"The projection took {result['projectMillis']} ms")

# We can use convenience methods on `G` to check if the projection looks correct
print(f"Graph '{G.name()}' node count: {G.node_count()}")
print(f"Graph '{G.name()}' node labels: {G.node_labels()}")
print(f"Graph '{G.name()}' relationship count: {G.relationship_count()}")

3. 特征向量中心性

特征向量中心性衡量节点基于其与其他网络中节点的连接的重要性或影响力。更高的特征向量中心性分数表明节点在网络中更具中心性和影响力。

对于我们的数据集，特征向量中心性可以帮助识别那些不仅自身连接良好，而且还与其他重要机场有连接的机场。具有高特征向量中心性的节点很可能是主要枢纽或连接广泛的机场。

eigenvector_centrality_result = gds.eigenvector.mutate(G, maxIterations=100, mutateProperty="eigenvectorCentrality")

# We can verify that the eigenvectorCentrality was mutated
G.node_properties()

我们可以使用以下代码查看我们的实现是否收敛，如果收敛，则查看其迭代次数

if eigenvector_centrality_result.didConverge:
    print(
        f"The number of iterations taken by Eigenvector Centrality to run is {eigenvector_centrality_result.ranIterations}."
    )
else:
    print("Algorithm did not converge!")

我们还可以使用以下代码查看特征向量中心性度量的分布。这将显示我们中心性度量的最小值、最大值、平均值和其他统计值。

eigenvector_centrality_result.centralityDistribution

我们现在将结果写回数据库。

gds.graph.nodeProperties.write(G, ["eigenvectorCentrality"])

利用特征向量中心性的结果，我们现在可以查找拥有主要枢纽或连接广泛的机场的前 20 个城市。

def display_top_20_cities(centrality_measure):
    """
    Function to execute the Cypher query to retrieve the top 20 cities with the highest centrality measure.
    """
    query = f"""
    MATCH (n:City)
    RETURN n.node_id AS node_id, n.name AS name, n.population AS population, n.{centrality_measure} AS {centrality_measure}
    ORDER BY n.{centrality_measure} DESC
    LIMIT 20
    """
    result = gds.run_cypher(query)

    # Display the result
    print(result)


display_top_20_cities("eigenvectorCentrality")

4. 介数中心性

介数中心性量化了节点作为网络中桥梁或中介的重要性。它衡量节点位于其他节点对之间最短路径上的频率。

对于我们的数据集，介数中心性高的城市/机场在没有直飞航班的机场之间充当关键的中转点或连接枢纽。它们在促进航空旅行流量方面发挥着重要作用，对于整体网络连接性至关重要。

betweenness_centrality_result = gds.betweenness.mutate(G, mutateProperty="betweennessCentrality")

# We can verify that the betweennessCentrality was mutated
G.node_properties()

我们还可以使用以下代码查看介数中心性度量的分布。这将显示我们中心性度量的最小值、最大值、平均值和其他统计值。

betweenness_centrality_result.centralityDistribution

我们现在将结果写回数据库。

gds.graph.nodeProperties.write(G, ["betweennessCentrality"])

利用介数中心性的结果，我们现在可以查找拥有机场作为关键中转点或连接枢纽的前 20 个城市，这些机场在没有直飞航班的机场之间发挥作用。

display_top_20_cities("betweennessCentrality")

5. 度中心性

度中心性衡量节点在网络中连接（边）的数量。

对于我们的数据集，度中心性高的城市与其他城市有大量的直飞航班连接。它们代表有许多直飞目的地或经常用于直飞旅行的城市。度中心性提供了对网络中单个机场的突出性和连接性的洞察。

degree_centrality_result = gds.degree.mutate(G, mutateProperty="degreeCentrality")

# We can verify that the degreeCentrality was mutated
G.node_properties()

与上面类似，我们还可以使用以下代码查看度中心性度量的分布。这将显示我们中心性度量的最小值、最大值、平均值和其他统计值。

degree_centrality_result.centralityDistribution

我们现在将结果写回数据库。

gds.graph.nodeProperties.write(G, ["degreeCentrality"])

最后，利用度中心性的结果，我们现在可以查找拥有大量直飞航班机场的前 20 个城市。

display_top_20_cities("degreeCentrality")

6. 清理

在结束之前，我们可以从 GDS 内存状态和数据库中清理示例数据。

# Cleanup GDS
G.drop()

# Cleanup database
gds.run_cypher("MATCH (n:City) DETACH DELETE n")

7. 参考资料

对于网络: Brendan J. Frey and Delbert Dueck. “Clustering by passing messages between data points.” Science 315.5814 (2007): 972-976.
对于城市元数据（大都市人口、纬度和经度）: Austin R. Benson, David F. Gleich, and Jure Leskovec. “Higher-order Organization of Complex Networks.” Science, 353.6295 (2016): 163–166.
数据集链接: https://snap.stanford.edu/data/reachability.html
Notebook 由 Kedar Ghule 贡献