中文摘要：

社区发现能够揭示真实社会网络的拓扑结构和动态特性.目前的社区发现算法多针对静态社会网络所设计,而绝大多数真实社会网络的社区结构是动态变化的.针对动态社区发现,现有算法通常基于社区结构平稳变化的假设,无法处理演化过程中可能出现的大量社区消亡或涌现等突发事件.为解决有效并高效地发现大规模动态社会网络的社区结构的问题,提出了一种基于邻域跟随关系的社区表示模型Follow-Community,模型刻画的社区由不同角色的节点以及节点间的跟随关系组成,通过发现节点间存在的直接或间接的跟随关系,可将跟随同一个节点的节点所构成的集合归为一个社区.基于该模型提出了一种具有接近线性时间复杂度的邻域跟随算法NFA（Neighborhood Following Algorithm）,遍历网络节点一次即可得到静态社会网络的社区结构.进一步扩展得到增量邻域跟随算法iNFA（incremental Neighborhood Following Algorithm）.通过更新网络演化过程中相关节点的邻域跟随关系,iNFA可发现动态社会网络的社区结构及社区演化.实验结果验证了算法在大规模动态社会网络社区发现方面具有精度、效率以及稳定性的优势.

英文摘要：

Community discovery can help reveal the topological structures and the dynamic characteristics of the real social networks.However,most community discovery algorithms are designed for static social networks,while in most real social networks,the community structures of networks change dynamically.For community discovery in dynamic social networks,existing algorithms are based on the assumption that the community structures of dynamic networks evolve smoothly,and therefore cannot deal with the sudden events of emergence and extinction of communities during the evolution of dynamic social networks.To address the aforementioned issue of discovering community structures effectively and efficiently in large-scale dynamic social networks,this paper presents a novel community representation model called Follow-Community model,which represents the following relationships among neighbors.In the Follow-Communitymodel,the community is represented by nodes with different roles and the following relationships among the nodes.By finding the direct or indirect following relationships among nodes,the collection of nodes that follow the same leader can be partitioned into one community.Based on the Follow-Community model,a Neighborhood Following Algorithm（NFA）with nearly linear time complexity is proposed to discover community structures in static social networks by just traversing the node set only once.Furthermore,an extended algorithm of NFA,named incremental Neighborhood Following Algorithm（iNFA）,is also proposed.By updating the neighborhood following relationships of the relevant nodes involved in network evolution over time,iNFA can discover the community structures and community evolution in dynamic social networks.Finally,extensive experiments are conducted to validate the advantage of the proposed algorithms in accuracy,efficiency and stability for community discovery in large-scale dynamic social networks.