7.4 社会网络的算法

大数据技术在会计与财务中的应用作者：张敏等2026/9/8《大数据技术在会计与财务中的应用》配套课件第7章·7.4社会网络的算法目录7.4.1PageRank7.4.2社区发现算法7.4社会网络的算法7.4社会网络的算法|02/13社会网络的算法随着网络多样性与复杂性的提升，仅依赖中心度、结构洞等特征已无法充分捕捉网络中蕴含的信息，如何更深入地刻画社会网络成为研究者日益关心的问题，一些更先进的算法也应运而生。本节将首先介绍基于有向图的节点重要性排序算法PageRank，然后介绍常见的社区发现算法。2026/9/8《大数据技术在会计与财务中的应用》配套课件7.4社会网络的算法|03/13社会网络的算法PageRankPageRank算法，又称网页排名算法，最初是由Google公司提出的对搜索引擎搜索结果中的网页进行排序的一种算法，现在也广泛应用于分析有向图中的节点重要程度。PageRank算法的基本思想是，重要的网页往往更多地被其他网页指向，即如果其他网页更频繁地指向某一个网页，则该网页也更重要。2026/9/8《大数据技术在会计与财务中的应用》配套课件7.4社会网络的算法|04/13社会网络的算法

2026/9/8《大数据技术在会计与财务中的应用》配套课件图7-8PageRank在社会网络中的应用示例7.4社会网络的算法|05/13社会网络的算法在python中，我们可以直接使用nx.pagerank()函数计算节点的PageRank值，结果如下所示。结果表明，节点D的PageRank值最高为0.45，而节点C的PageRank值最小为0.13。这也与我们的直觉一致，即A、B、C三个节点全部指向D，而没有节点指向C。In:nx.pagerank(G)Out:{‘A’:0.17121913703515862,‘B’:0.24398745873843833,‘D’:0.4513761585479028,‘C’:0.13341724567850016}2026/9/8《大数据技术在会计与财务中的应用》配套课件7.4社会网络的算法|06/13社会网络的算法社区发现算法大型社会网络中普遍存在若干“社区”。例如，一个学校有许多班级，通常一个班级内的同学彼此更熟悉，而不同班级间的同学关系较远、甚至没有来往。在这种情境下，每个班级即成为一个社区。社区发现（communitydetection）的目标是寻找社会网络中潜在的有特定关系的组织，探测网络中关系较为紧密的团体。常见的社区发现算法有Kernighan-Lin算法、Louvain算法等。2026/9/8《大数据技术在会计与财务中的应用》配套课件7.4社会网络的算法|07/13社会网络的算法（1）Kernighan-Lin算法Kernighan-Lin算法（K-L算法）是一种利用贪婪算法将社会网络划分为两个社区的二分法。K-L算法构造了一个目标函数Q，为社区内部的边数与社区之间的边数之差。理想的划分结果应该使得每个社区内较为紧密，即类内边数较多，而不同的社区间较为稀疏，即类间边数较少。因此，算法的优化目标是使得Q尽可能大。networkx模块提供了K-L的算法的函数kernighan_lin_bisection。基于networkx提供的空手道俱乐部的成员关系数据，以下代码展示了使用K-L算法对成员关系进行划分的结果。可以看到，该网络被划分为红色和蓝色两个社区，如图7-9所示。2026/9/8《大数据技术在会计与财务中的应用》配套课件7.4社会网络的算法|08/13社会网络的算法frommunityimportkernighan_lin_bisectionG=nx.karate_club_graph()com=list(kernighan_lin_bisection(G))print('社区数量：',len(com))print(com)pos=nx.spring_layout(G)nx.draw(G,pos,with_labels=True,node_color='w')color_list=['r','b']foriinrange(len(com)):nx.draw_networkx_nodes(G,pos,nodelist=com[i],node_color=color_list[i])plt.savefig('社区发现.jpg',dpi=600)plt.show()2026/9/8《大数据技术在会计与财务中的应用》配套课件图7-9基于K-L算法的社区划分结果7.4社会网络的算法|09/13社会网络的算法（2）Louvain算法Louvain算法是基于模块度（modularity）的社区发现算法，该算法的优点在于速度快、并且无须指定社区的数量，因此是当前学术界和工业界主流的社区发现算法之一。图7-10展示了Louvain算法的原理（Blondel等，2008）。第一，假设每个节点都是一个社区；第二，对每个节点i，尝试将节点i加入至其邻居节点j所在的社区。例如，尝试将节点0加入至节点2、3或5中，分别计算加入前后的模块度变化ΔQ，选择ΔQ最大（且大于0）的邻居节点加入，如果所有ΔQ均为负则保持不变；第三，重复第二步直到所有节点所属的社区不再变化；第四，将已划分出来的社区压缩为一个超节点，原社区内节点间的边的权重转化为新节点的环的权重；第五，重复第二步直至整个网络的模块度达到最大值。2026/9/8《大数据技术在会计与财务中的应用》配套课件7.4社会网络的算法|10/13社会网络的算法2026/9/8《大数据技术在会计与财务中的应用》配套课件图7-10Louvain算法的原理7.4社会网络的算法|11/13社会网络的算法在python中，我们可以调用python-louvain的community模块方便地应用Louvain算法。例如，继续沿用空手道俱乐部的社会网络G。调用community_louvain.best_partition()函数，指定分辨率为0.9。结果显示，0、1、2、3、7、11、12、13、17、19、21号成员归为第一组，8、9、14、15、18、20、22、23、26、27、29、30、32、33号成员归为第二组，4、5、6、10、16号成员归为第三组，24、25、28、31号成员归为第四组。pipinstallpython-louvainimportcommunityascommunity_louvainpartition=community_l