Leiden算法简介：Python实现网络分区

大家好！今天我们来深入了解Leiden算法，这是一个用于网络分区的强大工具。我们将使用Python来实现这个算法，并通过一个实际的例子来展示它的工作原理。

1. Leiden算法简介

Leiden算法是一种用于社区检测的算法，它可以帮助我们在复杂的网络中找到紧密相连的群体。想象你要给一个大班级的学生分组，希望每个小组内的同学关系都很好，Leiden算法就是来解决这类问题的。

2. Python代码实战

让我们用Python来实际操作一下！我们将创建一个同学关系网络，然后使用Leiden算法来进行分组。

import networkx as nx
from graspologic.partition import hierarchical_leiden

# 创建同学关系图
G = nx.Graph()
students = [
    "张三", "李四", "王五", "赵六", "孙七", "周八", "吴九", "郑十", 
    "钱十一", "朱十二", "陈十三", "林十四", "黄十五", "杨十六", "刘十七", 
    "何十八", "高十九", "马二十", "范二一", "程二二"
]
G.add_nodes_from(students)

# 添加同学关系
relationships = [
    ("张三", "李四"), ("张三", "王五"), ("李四", "赵六"), ("王五", "孙七"),
    ("赵六", "周八"), ("孙七", "吴九"), ("周八", "郑十"), ("吴九", "钱十一"),
    ("郑十", "朱十二"), ("钱十一", "张三"), ("朱十二", "李四"), ("陈十三", "林十四"),
    ("黄十五", "杨十六"), ("刘十七", "何十八"), ("高十九", "马二十"), ("范二一", "程二二"),
    ("张三", "陈十三"), ("李四", "黄十五"), ("王五", "刘十七"), ("赵六", "高十九"),
    ("孙七", "范二一"), ("周八", "林十四"), ("吴九", "杨十六"), ("郑十", "何十八"),
    ("钱十一", "马二十"), ("朱十二", "程二二")
]
G.add_edges_from(relationships)

# 使用Leiden算法进行分组
result = hierarchical_leiden(
    graph=G,
    max_cluster_size=5,  # 每组最多5人
    extra_forced_iterations=3  # 多尝试三次，看看有没有更好的分法
)

# 打印完整的分组结果
print("完整的分组结果：")
for cluster in result:
    print(cluster)

# 整理并打印最终分组
final_groups = {}
for cluster in result:
    if cluster.is_final_cluster:
        if cluster.cluster not in final_groups:
            final_groups[cluster.cluster] = []
        final_groups[cluster.cluster].append(cluster.node)

print("\n最终分组结果：")
for group_num, members in final_groups.items():
    print(f"第{group_num + 1}组：{', '.join(members)}")

3. 分组结果解读

运行上面的代码，我们得到了以下结果：

完整的分组结果：
HierarchicalCluster(node='李四', cluster=0, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='黄十五', cluster=0, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='吴九', cluster=0, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='杨十六', cluster=0, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='王五', cluster=1, parent_cluster=None, level=0, is_final_cluster=False)
HierarchicalCluster(node='朱十二', cluster=1, parent_cluster=None, level=0, is_final_cluster=False)
HierarchicalCluster(node='孙七', cluster=1, parent_cluster=None, level=0, is_final_cluster=False)
HierarchicalCluster(node='刘十七', cluster=1, parent_cluster=None, level=0, is_final_cluster=False)
HierarchicalCluster(node='范二一', cluster=1, parent_cluster=None, level=0, is_final_cluster=False)
HierarchicalCluster(node='郑十', cluster=1, parent_cluster=None, level=0, is_final_cluster=False)
HierarchicalCluster(node='何十八', cluster=1, parent_cluster=None, level=0, is_final_cluster=False)
HierarchicalCluster(node='程二二', cluster=1, parent_cluster=None, level=0, is_final_cluster=False)
HierarchicalCluster(node='张三', cluster=2, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='陈十三', cluster=2, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='周八', cluster=2, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='林十四', cluster=2, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='钱十一', cluster=3, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='赵六', cluster=3, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='高十九', cluster=3, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='马二十', cluster=3, parent_cluster=None, level=0, is_final_cluster=True)
HierarchicalCluster(node='王五', cluster=4, parent_cluster=1, level=1, is_final_cluster=True)
HierarchicalCluster(node='刘十七', cluster=4, parent_cluster=1, level=1, is_final_cluster=True)
HierarchicalCluster(node='孙七', cluster=5, parent_cluster=1, level=1, is_final_cluster=True)
HierarchicalCluster(node='范二一', cluster=5, parent_cluster=1, level=1, is_final_cluster=True)
HierarchicalCluster(node='朱十二', cluster=6, parent_cluster=1, level=1, is_final_cluster=True)
HierarchicalCluster(node='程二二', cluster=6, parent_cluster=1, level=1, is_final_cluster=True)
HierarchicalCluster(node='郑十', cluster=7, parent_cluster=1, level=1, is_final_cluster=True)
HierarchicalCluster(node='何十八', cluster=7, parent_cluster=1, level=1, is_final_cluster=True)

最终分组结果：
第1组：李四, 黄十五, 吴九, 杨十六
第3组：张三, 陈十三, 周八, 林十四
第4组：钱十一, 赵六, 高十九, 马二十
第5组：王五, 刘十七
第6组：孙七, 范二一
第7组：朱十二, 程二二
第8组：郑十, 何十八

让我们来解读这个结果：

level=0：初步分组

在 level=0 中，算法将所有学生分成了四个大组：

1. 第一个组（cluster=0）：包含李四、黄十五、吴九、杨十六
2. 第二个组（cluster=1）：包含王五、朱十二、孙七、刘十七、范二一、郑十、何十八、程二二
3. 第三个组（cluster=2）：包含张三、陈十三、周八、林十四
4. 第四个组（cluster=3）：包含钱十一、赵六、高十九、马二十

注意，第一、三、四组在这个级别就已经是最终结果了（is_final_cluster=True）。

level=1：细分小组

在 level=1 中，算法进一步将第二个大组（cluster=1）细分成了四个小组：

1. 王五、刘十七（cluster=4）
2. 孙七、范二一（cluster=5）
3. 朱十二、程二二（cluster=6）
4. 郑十、何十八（cluster=7）

这些小组都是最终的分组结果（is_final_cluster=True）。

4. 为什么会这样分组？

Leiden算法在分组时考虑了整个网络的结构，而不仅仅是直接的关系。例如：

1. 李四、黄十五、吴九、杨十六被分在一组，可能是因为他们之间有较多的直接或间接联系。
2. 虽然有些同学之间有直接联系（如张三和李四），但他们没有被分在一组，这可能是因为整体来看，将他们分开可以使得每个小组内部的关系更加紧密。
3. 一些组只有两个人（如王五和刘十七），这可能是因为算法认为他们之间的关系特别紧密，或者他们与其他同学的关系相对较弱。

5. Leiden算法的工作原理

1. 初步分组：算法首先根据网络结构将节点分成几个大的社区（在我们的例子中是4个）。
2. 优化：然后，算法会尝试移动节点到不同的社区，以提高整体的模块度（衡量网络划分质量的指标）。
3. 细化：最后，算法会在需要的情况下对大社区进行进一步的划分，形成更小的子社区（如我们例子中的第二个大组）。

整个过程会重复多次（在我们的例子中是3次，由 extra_forced_iterations=3 决定），以找到最优的分组方案。

6. 实际应用

Leiden算法不仅可以用于学生分组，还有很多其他应用：

1. 社交网络分析：发现社交网络中的兴趣小组或社区。
2. 生物信息学：分析蛋白质相互作用网络，发现功能相关的蛋白质群。
3. 交通网络优化：识别城市中的社区结构，优化公共交通路线。
4. 推荐系统：通过对用户进行分组，提供更精准的推荐。

7. 给初学者的建议

1. 实验不同的参数：尝试改变 max_cluster_size 和 extra_forced_iterations，看看结果会有什么变化。
2. 可视化网络：使用 NetworkX 库的绘图功能，将关系网络可视化，这样可以更直观地理解算法的工作原理。
3. 尝试不同的数据集：你可以创建不同的关系网络，看看算法在不同情况下的表现。
4. 理解随机性：注意，Leiden算法可能会因为随机性而在不同运行中产生略有不同的结果。这是正常的，也反映了实际网络中社区结构的复杂性。

8. 总结

通过这个详细的例子，我们看到了Leiden算法如何在复杂的网络中找到紧密相连的群体。虽然算法的内部工作原理可能很复杂，但使用Python实现起来并不困难。

这个算法的结果可能会让我们感到惊讶：有些看似应该在一起的同学被分开了，而一些看似关系不那么密切的同学却被分到了一起。这正体现了网络结构的复杂性，以及Leiden算法考虑整体网络结构的特点。

记住，编程和算法学习最重要的是实践。尝试修改代码，创建你自己的网络，看看会得到什么有趣的结果。祝你学习愉快，编程之路越走越远！

原文地址：https://blog.csdn.net/engchina/article/details/142425223

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！