基于广度优先搜索的局部社区发现算法

doi:10.3969/j.issn.1000-3428.2015.10.008

计算机工程

基于广度优先搜索的局部社区发现算法

王豫中,范磊,李建华

(上海交通大学电子信息与电气工程学院,上海 200240)

收稿日期:2014-09-02 出版日期:2015-10-15 发布日期:2015-10-15
作者简介:王豫中(1990－),男,硕士研究生,主研方向:社交网络,数据挖掘;范磊,副教授;李建华,教授。
基金资助:
国家“973”计划基金资助项目(2013CB329603);上海市科委基础研究领域基金资助项目(13JC1403500)。

Local Community Discovery Algorithm Based on Breadth-first Search

WANG Yuzhong,FAN Lei,LI Jianhua

(School of Electronic Information and Electrical Engineering,Shanghai Jiaotong University,Shanghai 200240,China)

Received:2014-09-02 Online:2015-10-15 Published:2015-10-15

摘要/Abstract

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

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

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

中图分类号:

TP391

王豫中,范磊,李建华. 基于广度优先搜索的局部社区发现算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2015.10.008.

WANG Yuzhong,FAN Lei,LI Jianhua. Local Community Discovery Algorithm Based on Breadth-first Search[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2015.10.008.

http://www.ecice06.com/CN/Y2015/V41/I10/37

参考文献

参考文献［1］Jonsson P F,Cavanna T,Zicha D,et al.Cluster Analysis of Networks Identification of Important Protein Com-munities Involved in Cancer Metastasis［J］.BMC Bioin-formatics,2006,6(7):2-9. ［2］蔡波斯,陈翔.基于行为相似度的微博社区发现算法研究［J］.计算机工程,2013,39 (8):55-59. ［3］熊正理,姜文君,王国军.基于用户紧密度的在线社会网络社区发现算法［J］.计算机工程,2013,39 (8):50-54. ［4］Dourisboure Y,Geraci F,Pellegrini F.Extraction and Classification of Dense Communities Int-the Web［C］//Proceedings of the 16th International Conference on World Wide Web.Washington D.C.,USA:IEEE Press,2007:461-470. ［5］Girvan M,Newman M E.Community Structure in Socialand Biological Networks［J］.Sciences of the United States of America,2002,99(12):7821-7826. ［6］郭进时,汤红波,葛国栋.一种联合拓扑与属性的社区模糊划分算法［J］.计算机工程,2013,39 (11):35-40. ［7］Li Xiang,Chen Guanrong.A Local-world Evolving Network Model［J］.Physical A:Statistical Mechanics and Its Applications,2003,328(1/2):274-286. ［8］Clauset A.Finding Local Community Structure in Networks［J］.Physical Review E,2005,72(2). ［9］Luo Feng,Wang J Z,Promislow E.Exploring Local Community Structures in Large Networks［C］//Proceedings of 2006 IEEE/WIC/ACM International Conference on Web Intelligence.Washington D.C.,USA:IEEE Press,2006:233-239. ［10］Lancichinetti A,Fortunato S,Kertesz J.Detecting the Overlapping and Hierarchical Community Structure in Complex Networks［J］.New Journal of Physics,2009,11(3). ［11］Girvan M,Newman ME.Finding and Evaluating Community Structure in Networks［J］.Physical Review E,2004,69(2). ［12］Newman M E.Modularity and Community Structure in Networks［J］.Sciences of the United States of America,2006,103(23):8857-8882. ［13］Acua M A,Dorso G.Detection of Community Structures in Networks via Global Optimization［J］.Physica A:Statistical Mechanics and Its Applications,2005,538(1):593-604. ［14］Jure L,Kevin J L,Anirban D,et al.Community Structure in Large Networks:Natural Cluster Sizes and the Absence of Large Well-defined Clusters［EB/OL］.(2009-10-21).http://projecteuclid.org/euclid.im. ［15］Newman M E.Fast Algorithm for Detecting Community Structure in Networks［J］.Physical Review E,2004,69(6). ［16］Gibson D,Kumar R,Tomkins A.Discovering Large Dense Subgraphs in Massive Graphs［C］//Proceedings of the 31st International Conference on Very Large Bases Databases.Washington D.C.,USA:IEEE Press,2005:721-732. ［17］Fortunato S.Community Detection in Graphs［J］.Phy-sics Reports,2010,486(3):75-174. 编辑索书志

[1]	程小辉, 李钰, 康燕萍. 基于中间图特征提取的卷积网络双标准剪枝[J]. 计算机工程, 2023, 49(3): 105-112.
[2]	李嘉伟, 张激, 赵俊才, 丁如艺. 一种SRIO网络负载均衡最短路径路由算法[J]. 计算机工程, 2020, 46(3): 214-221,228.
[3]	朱国晖, 康潇轩, 雷兰洁. 基于最优子网的虚拟网络映射算法[J]. 计算机工程, 2019, 45(10): 8-12.
[4]	冯曦,朱福喜,刘世超. 基于深度游走模型的标签传播社区发现算法[J]. 计算机工程, 2018, 44(3): 220-225,232.
[5]	高峰,刘震,高辉. 结合有监督广度优先搜索策略的通用垂直爬虫方法[J]. 计算机工程, 2018, 44(11): 289-299.
[6]	姚洁,朱响斌,宋新方,李广龙,邱慧玲. 基于节点排序的贝叶斯网络结构学习算法[J]. 计算机工程, 2017, 43(5): 317-321.
[7]	王爽,冯志勇. 基于语义数据的药物网络模型构建与分析[J]. 计算机工程, 2016, 42(6): 31-36.
[8]	吴钟刚,吕钊. 一种基于局部相似性的社区发现算法[J]. 计算机工程, 2016, 42(12): 196-203.
[9]	赵学锋. 求解最小连通r-跳k-支配集的启发式算法[J]. 计算机工程, 2012, 38(21): 67-69,73.
[10]	鄢靖丰, 陶少华, 夏方玉. 基于单元树结构的广度优先P2P搜索算法[J]. 计算机工程, 2011, 37(9): 135-137.
[11]	王桂平, 张帅. 基于双向广度优先搜索的魔力方块问题求解[J]. 计算机工程, 2011, 37(20): 219-222.
[12]	徐强;孙乐昌;单洪;赵亭. 基于BFS的轻量级P2P搜索模型[J]. 计算机工程, 2009, 35(3): 106-108,.
[13]	王明福. 一种求解关键路径的新算法[J]. 计算机工程, 2008, 34(9): 106-108.

选择文件类型/文献管理软件名称

选择包含的内容

基于广度优先搜索的局部社区发现算法

Local Community Discovery Algorithm Based on Breadth-first Search

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于广度优先搜索的局部社区发现算法

Local Community Discovery Algorithm Based on Breadth-first Search

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价