社区发现

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

本笔记本展示了如何使用 graphdatascience 库在 Reddit 超链接网络数据集上进行社区检测，数据集可在此处下载。我们将使用 soc-redditHyperlinks-body.tsv 文件。

本示例涉及的任务包括使用弱连接组件（Weakly Connected Components）进行初始图预处理，然后在最大组件上使用 Louvain 算法进行社区检测。

1. 设置

首先，我们要导入依赖项并建立 GDS 客户端与数据库的连接。

此外，您可以使用 Aura Graph Analytics，并跳过下方整个“设置”部分。

# 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://: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 DataFrame。这里只使用数据集的一个子集，抽样数据仅到 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 列指示源 subreddit 与目标 subreddit 之间是正向 (+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()

接下来，我们获取所有唯一节点（源或目标）的列表，并将其加载为 DataFrame。

# 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. 弱连接组件

图数据集不一定是连通的。也就是说，图中可能不存在从每个节点到每个其他节点的路径（子图之间可能根本不相连）。因此，需要统计每个子图中的节点总数，以判断其是否足够大以进行进一步的图分析。较小的子图或孤立节点不会对社区检测任务产生贡献，应该被剔除。弱连接组件（Weakly Connected Components）通常是图预处理的早期步骤之一。

我们使用 Weakly Connected Components 算法来找到相连节点的集合，并为每个集合分配一个组件 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")

我们的社区检测算法得到的模块度（modularity）得分为 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. 网络上的社区互动与冲突. 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