摘要
对现有的社会网络社团发现算法进行研究,发现存在算法时间复杂度高、准确率低和没有充分利用节点属性信息等问题,提出了一种基于节点相似度的社团发现算法以解决这些问题。综合考虑图的拓扑结构和节点属性信息,结合构造属性扩展图的思想和基于结构情境相似度的思想得到节点的相似度,利用改进的K-means算法对所有节点进行聚类得到社团结构。编程实验结果表明,使用该算法得到的社团准确率较高,算法的时间复杂度为线性的,在带属性的数据集上和不带属性的数据集上的测试结果均验证了算法的有效性。
With study of the existing community detection algorithms in social networks, problems of high time complexity, low accuracy rate and the neglect of node attributes information are found, and a new community detection algorithm based on node similarity is presented to solve it. The algorithm takes composite factor of topological structure and node attributes into account. At first, the idea of constructing attribute augmented graph with attribute nodes gained from node attributes, and calculating nodes similarity based on graph structure are used together to gain node similarity. And then, an improved K-means algorithm based on node similarity is proposed to cluster nodes to detect implied communities. Through programming realization, higher accuracy rate and a linear time complexity are showed in final experimental results. The effectiveness of the algorithm is verified on an artificial two community dataset with attributes and two standard datasets without attributes.
出处
《计算机工程与设计》
CSCD
北大核心
2014年第5期1688-1693,共6页
Computer Engineering and Design
基金
国家自然科学基金项目(61003311)
安徽高校省级自然科学研究基金项目(KJ2011A039)
关键词
社会网络
社团发现
图的拓扑结构
节点属性
属性扩展图
结构化相似度
social network
community detection
topological structure
node attribute
attribute augmented graph
structural similarity
