计算机论文哪里有？本文处理的是无向无权的静态网络，如何在有向网络、有权网络和动态网络中利用节点间的局部路径信息进行社区发现，需要进一步去探索。
1 绪论
1.2 国内外研究现状
重叠社区发现已成为图聚类问题的重要研究热点，目前已经提出一些成功的重叠社区发现算法，如基于派系过滤的、基于标签传播的、基于局部扩展的和基于边划分的方法等[4]。
1.2.1 基于派系过滤的算法
2005年Palla等提出派系过滤算法CPM[5]，首先发现网络中的所有k-团并对其进行合并形成k-团社区，位于多个k-团社区中的公共节点即为重叠节点。为了提升寻找k-团的效率，2008年Kumpula等提出CPM的改进算法SCP算法[6]，该算法从一个空网络开始，按照一定顺序将边添加到网络中，在添加边的过程中发现k-团从而发现重叠社区结构，时间复杂度与网络中k-团数量成线性关系[7]。CPM算法和SCP算法不同k值得到的社区发现结果差异较大且无法划分k-团社区外的节点。2009年Shen等提出EAGLE算法[8]，将网络中的最大团和单独节点看作初始社区，不断合并相似度最高的社区得到树状图，根据扩展模块度EQ选择最佳重叠社区结构，然而扩展模块度存在分辨率限制问题，无法发现规模较小的社区。2014年Maity等提出ECPM算法[9]，首先通过CPM算法找到初始社区，通过计算节点与社区间的直接连边占比处理未聚类节点，然而仅根据节点与社区间的直接连边信息无法准确度量节点与社区连接的紧密程度。为了提高寻找网络中最大团的效率，2018年Jabbour等[10]提出利用弦图寻找最大团并将其作为初始社区，通过不断添加社区的邻居节点使导电性值达到最优。2022年Sun等[11]首先改进CPM算法发现网络中由k-团形成的模块度较大的初始社区，再采用基于社区的影响力传播模型对初始社区进行扩展以发现重叠节点。由于寻找网络中的最大团是NP困难问题，同时团的限制过于严格，Zhang等提出WCPM算法[12]识别网络中由种子集构成的弱团，合并相似度高的弱团来发现重叠社区，由于弱团由两个相邻节点的公共邻居组成，其时间复杂度与网络边数成线性关系。
基于派系过滤的方法通过寻找网络中的k-团进行社区发现，然而寻找网络中的最大团是NP困难问题。同时，这类方法假设社区内节点间形成较多三角形连接，不适用于社区内部连接相对稀疏的网络。因此基于派系过滤的方法仅适用于发现小规模网络中连接稠密的社区结构[13]。
3 基于局部路径扩展的重叠社区发现算法
3.1 局部路径支持度
社区内节点间通常会通过一些特殊连接模式相互连通，如直接连边或三角形连接模式，利用这些特殊连接模式衡量社区显著性可以有效发现网络中的社区结构。然而，当社区内部连接相对稀疏时，社区内节点间的直接连边或三角形连接不足以刻画社区结构。路径连通性是对社区结构一种更通用的描述，社区内节点间的路径连通性通常比社区间节点的连通性更强，即处于同一社区的节点间往往通过多条短路径相互连接。然而，已有的社区适应度函数无法利用连边密度或三角形密度有效度量社区内节点间的路径连通性。针对此，本文首先提出一种基于局部路径支持度的社区适应度函数，对社区内相邻节点间的路径连通性进行度量。
基于局部l-路径支持度的适应度函数根据社区内节点间的路径连通性有效度量了社区内部节点间连接的紧密程度。该适应度函数值越大，则社区C内节点间的连接更多的出现在社区内部，更少与社区外的其余节点发生联系。通过该适应度函数可以发现社区内部通过较多短路径相互连接的社区结构。
图3.1给出了两个节点数及边数相同的社区C1和C2，节点v21为未聚类节点，与C1和C2连边数相同。表3.1中第1-4行分别给出了由式(2.1)-(2.4)所计算的社区适应度，其中第2列和第4列是C1和C2的社区适应度值，第3列和第5列是将v21分别加入C1或C2所得社区的适应度值。可以看到，由于社区节点数和边数相同，式(2.1)-(2.4)给出的适应度函数无法区分两个社区的结构显著性，也无法区分节点v21的加入对社区结构的影响。但实际上，尽管C1和C2边数相同，但在C1内部节点间有更多的短路径相互连通，比C2的路径连通性更好。而在加入节点v21后，C2的节点间通过 v21形成更多短路径相互连接，而v21对C1中节点间的连通性影响较小，因此社区C2∪{v21}应比C1∪{v21}的适应度值更高。
4 改进的局部路径扩展重叠社区发现算法
4.1 问题描述
LPEO算法在对初始种子进行扩展之后，得到的社区结构中通常有较多的重叠节点，而重叠节点的邻居节点具有较大的邻域标签熵，在根据邻域标签熵更新社区种子集时，只有少数节点被更新为新种子，这导致对新种子集进行扩展时聚类节点越来越少，从而产生大量的未聚类节点。如图4.1和表4.1分别给出了LPEO在Dolphins网络中扩展初始种子得到的社区结构以及此时已聚类节点的邻域标签熵，表4.2给出了第1次更新得到的种子集，迭代更新并扩展每个社区种子集直到社区结构稳定后，未聚类节点数量为28个。
此外，随着网络规模的增大，每个社区内部通常存在一个核心节点子集，而不同社区的核心节点子集通常互不重叠。为了在社区种子集更新过程中可以逐渐扩大社区核心的规模，并减少未聚类节点数量，本章先得到网络的一种非重叠社区划分结构，再根据节点邻域标签熵得到社区核心。
4.2 改进的局部路径扩展重叠社区发现算法
4.2.1 初始社区划分
标签传播算法具有接近线性的时间复杂度[49]，可以快速有效地发现网络中的非重叠社区结构，因此首先采用标签传播算法对网络进行预处理。图4.2给出了Dolphins网络上利用标签传播算法得到的一种社区划分结果。
表4.3给出了标签传播算法在几个真实网络上发现社区个数的平均值。可以看出与真实社区结构相比，标签传播算法通常会得到较多社区，其中包含一些小社区。对于只包含2个节点的社区，由于其没有构成社区结构，直接删除。为了得到社区内部节点间紧密连接的社区结构，根据公式(3.1)给出的基于局部路径支持度的适应度函数合并能够提高社区适应度的社区，若两个社区的合并可以提高适应度值，则合并这两个社区。图4.3给出了Dolphins网络利用适应度函数合并后的社区划分结果。通过社区间的合并，一些小社区合并到大社区中，得到了社区内部节点间路径连通性较好的社区结构。
5 总结与展望
5.2 展望
从局部路径连通性角度进行社区发现可以发现内部路径连通性强的社区结构。本文处理的是无向无权的静态网络，如何在有向网络、有权网络和动态网络中利用节点间的局部路径信息进行社区发现，需要进一步去探索。同时在实际网络中，路径连通性可能仍无法准确刻画不同网络中社区的连接模式，如何发现网络中具有特定连接方式的模体，进而发现重叠社区结构是值得深入研究的课题。
此外，随着现实世界网络规模的高速增长，传统的重叠社区发现算法在计算效率上具有较大局限性，深度学习可以处理大规模网络，但现有的基于深度学习的社区发现算法并没有充分利用节点间的拓扑结构，如何充分利用网络的拓扑信息并与属性信息相结合来进行重叠社区发现是未来需要继续研究的课题。
参考文献（略）
