Abstract: Overlapping community detection is a major topic in complex network research. To improve the time efficiency of detection overlapping communities in the network, it proposes a link-based streaming overlapping community detection algorithm called LBSA. The algorithm firstly deals with the edges of the link graph in random order to get the initial communities, then merges the small overlapping communities with other the most similarly large communities. Through those two steps, the algorithm can get the overlapping structure of network with nearly linear time complexity. Experimental results show that the algorithm can detect the overlapping communities in the network with better time efficiency and has good performance compared to the other algorithms.

Key words: graph streaming, overlapping community detection, edge clustering coefficient, link graph, community similarity

摘要： 重叠网络的社区发现是复杂网络研究中的重要问题。为了提高网络中重叠社区发现的时间效率，提出一种基于边图的线性流重叠社区发现算法LBSA。算法首先对于边图网络中的边进行随机的依次处理，完成节点的初步社区划分，再将其中重叠小社区合并到相似度最大的其他大社区中得到最终的社区。通过以上步骤，算法能够以接近线性的时间复杂度得到网络的重叠结构。从最终的实验结果来看，与其他算法相比，该算法能够在更短的时间有质量地发现网络中的重叠社区。

关键词: 流式图, 重叠社区发现, 边聚类系数, 边图, 社区相似度