针对有向图的局部扩展的重叠社区发现算法

摘要：

当前社区发现算法主要是针对无向图研究社区结构，但在实际复杂网络中，链接关系时常表现出非对称性或方向性，比如Twitter的用户关注关系，文献网络的引用关系，网页之间的超链接关系等应用网络。因此，本文依据信息在复杂网络中的传播规律和流动方向性，提出了k‐Path共社区邻近相似性概念及计算方法，用于衡量结点在同一社区的相似性程度，并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法（Local and wave‐like extension algorithm of detecting overlapping community ，LWS‐OCD）。在真实数据集上的实验表明，共社区邻近相似性概念实现了有向到无向的合理转换，而且提高了社区结点的聚集效果，LWS‐OCD算法能够有效地发现带权无向图中的重叠社区。

关键词：有向图、社区发现、共社区邻近相似性、带权无向图、重叠社区

分类号：TP391(计算技术、计算机技术)

资助基金：中国人民大学科学研究基金中央高校基本科研业务费专项资金10XNI029资助项目；国家自然科学基金70871001，71271211资助项目；北京市自然科学基金4132067资助项目。

在线出版日期：2015-07-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：683-693