社区检测

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

该笔记本演示了 graphdatascience 库在 Reddit 超链接网络数据集（可从此处下载）上进行社区检测的用法。我们将使用 soc-redditHyperlinks-body.tsv 文件。

我们在此处涵盖的任务包括使用弱连接组件进行初始图预处理，然后使用 Louvain 算法对最大组件进行社区检测。

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(2, 5, 0)

2. 导入数据集

我们首先将数据集导入为 Pandas 数据帧。我们只使用数据集的一个子集。采样数据只到 2014 年 3 月 1 日。

df = pd.read_csv("https://snap.stanford.edu/data/soc-redditHyperlinks-body.tsv", sep="\t")
df = df[df["TIMESTAMP"] < "2014-03-01 02:51:13"]
df.head()

LINK_SENTIMENT 列表示源子版块到目标子版块是否存在正向 (+1) 或负向 (-1) 关系。我们过滤掉负向情感关系，因为它们不会对任何有意义的社区有所贡献。我们还会删除重复关系。

relationship_df = df[df["LINK_SENTIMENT"] == 1]
columns = ["SOURCE_SUBREDDIT", "TARGET_SUBREDDIT"]
relationship_df = relationship_df[columns]
relationship_df = relationship_df.drop_duplicates()
relationship_df.head()

接下来，我们获取所有不重复节点（源或目标）的列表，并将其加载为数据帧。

# Get unique nodes for each column
source_nodes = pd.Series(df["SOURCE_SUBREDDIT"])
target_nodes = pd.Series(df["TARGET_SUBREDDIT"])
# Get unique nodes for both columns
all_nodes = pd.Series(pd.concat([df["SOURCE_SUBREDDIT"], df["TARGET_SUBREDDIT"]])).unique()

# Create new dataframe with distinct nodes
nodes_df = pd.DataFrame({"SUBREDDIT": all_nodes})
nodes_df.head()

最后，我们将这些数据（节点和边）加载到图数据库和 GDS 图中。

gds.run_cypher(
    "UNWIND $nodes AS node CREATE (n:Subreddit {name: node.SUBREDDIT})",
    params={"nodes": nodes_df.to_dict("records")},
)

gds.run_cypher(
    """
    UNWIND $rels AS rel
    MATCH (source:Subreddit {name: rel.SOURCE_SUBREDDIT}), (target:Subreddit {name: rel.TARGET_SUBREDDIT})
    CREATE (source)-[:HYPERLINKED_TO]->(target)
    """,
    params={"rels": relationship_df.to_dict("records")},
)

G, result = gds.graph.project("reddit", "Subreddit", "HYPERLINKED_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()}")

gds.graph.list()

3. 弱连接组件

图数据集不一定总是连接的。也就是说，图中可能不存在从每个节点到其他所有节点的路径（图中的子图之间可能完全不连接）。因此，我们需要找到每个子图中的节点总数，以查看它是否足够大，可以进行进一步的图分析。较小的子图或孤立节点不会对社区检测任务有所贡献，应该被淘汰。弱连接组件通常是图预处理的早期步骤之一。

我们使用弱连接组件算法来查找连接节点的集合，并为每个集合分配一个组件 ID。

result = gds.wcc.mutate(G, mutateProperty="componentId")

print(f"Components found: {result.componentCount}")

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

接下来，我们将查看每个连接组件的大小，并根据此选择需要进一步分析的子图。

我们在此处使用 run_cypher 而不是直接的 GDS 客户端调用，因为我们希望查看连接组件的大小。

query = """
    CALL gds.graph.nodeProperties.stream('reddit', 'componentId')
    YIELD nodeId, propertyValue
    WITH gds.util.asNode(nodeId).name AS node, propertyValue AS componentId
    WITH componentId, collect(node) AS subreddits
    WITH componentId, subreddits, size(subreddits) AS componentSize
    RETURN componentId, componentSize, subreddits
    ORDER BY componentSize DESC
"""

components = gds.run_cypher(query)
components

largest_component = components["componentId"][0]

print(f"The largest component has the id {largest_component} with {components['componentSize'][0]} subreddits.")

为了进行进一步的分析，我们将只处理该子图。

largest_component_graph, _ = gds.graph.filter(
    "largest_connected_components", G, f"n.componentId={largest_component}", "*"
)
largest_component_graph

4. 使用 Louvain 进行社区检测

我们使用 Louvain 算法来检测子图中的社区，并为每个社区分配一个 louvainCommunityId。

gds.louvain.mutate(largest_component_graph, mutateProperty="louvainCommunityId")

我们的社区检测算法获得了 0.5898 的模块度分数。

gds.graph.nodeProperties.write(largest_component_graph, ["louvainCommunityId"])

我们还可以通过以下命令检查属性是否已写入。

gds.run_cypher(
    """
    MATCH (n) WHERE 'louvainCommunityId' IN keys(n)
    RETURN n.name, n.louvainCommunityId LIMIT 10
    """
)

现在我们要检查 Louvain 生成的社区。

query = """
    CALL gds.graph.nodeProperties.stream('largest_connected_components', 'louvainCommunityId')
    YIELD nodeId, propertyValue
    WITH gds.util.asNode(nodeId).name AS node, propertyValue AS communityId
    WITH communityId, collect(node) AS subreddits
    WITH communityId, subreddits, size(subreddits) AS communitySize
    RETURN communityId, communitySize, subreddits
    ORDER BY communitySize DESC
"""

communities = gds.run_cypher(query)
communities

5. 进一步的思路

使用 Bloom 检查生成的社区。您可以根据社区属性使用基于规则的样式设置。
尝试调整 Louvain 的更多参数，看看社区有何不同。
尝试使用 GDS 文档中列出的其他社区检测算法。

6. 清理

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

# Cleanup GDS
largest_component_graph.drop()
G.drop()

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

7. 参考文献

Srijan Kumar, William L. Hamilton, Jure Leskovec, and Dan Jurafsky. 2018. Community Interaction and Conflict on the Web. In Proceedings of the 2018 World Wide Web Conference (WWW ’18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 933–943. https://doi.org/10.1145/3178876.3186141