Abstract: Local community detection is a hot topic in network topology research recently,this paper proposes a local community detection algorithm based on a given node.This algorithm starts from original node,finds the max connective node relevant to the original node,uses Breadth-first Search(BFS) based on node similarity to find local community,and cuts off the found community and gets the entire community which contains the original node.Experimental result shows that this algorithm reduces the time complexity to O(kd3) with high accuracy.

Key words: max associativity, common number of friends, node similarity, Breadth-first Search(BFS), local community detection

摘要： 局部社区发现是网络拓扑研究中的热点,从起始节点的最大结合性节点出发,提出一个基于给定节点的局部社区发现算法。对整个社区进行广度优先搜索(BFS),从起始节点开始找到最大结合性节点,基于节点相似度(共同好友数目)并且利用BFS进行社区发现,对所发现的社区进行剪枝策略,从而得到起始节点所在的局部社团。实验结果证明,该算法在不降低精度的前提下,时间复杂度为O(kd3)。

关键词: 最大结合性, 共同好友数, 节点相似度, 广度优先搜索, 局部社区发现

CLC Number: 

• TP391