基于节点间的依赖程度划分网络中社团的算法

计算机与现代化

基于节点间的依赖程度划分网络中社团的算法

1.廊坊职业技术学院基础部，河北廊坊065000；2.河北工业大学理学院,天津300401

收稿日期:2013-12-23 出版日期:2014-04-17 发布日期:2014-04-23
作者简介:作者简介：高洪伟(1978)，女，河北霸州人，廊坊职业技术学院基础部讲师，硕士，研究方向：运筹与优化；徐勇（1971），男，天津人，河北工业大学理学院副教授，博士，研究方向：线性系统理论，预测控制。
基金资助:

基金项目：河北省自然科学基金资助项目（A2013202198）

Detecting Communities of Complex Networks Based on Dependence Degree of Two Nodes

1. Department of Basic, Langfang Polytechnic Institute, Langfang 065000, China;


2. College of Science, Hebei University of Technology, Tianjin 300401, China

Received:2013-12-23 Online:2014-04-17 Published:2014-04-23

摘要/Abstract

摘要：

摘要：寻找复杂网络中的社团结构对于理解复杂网络的结构和功能有十分重要的意义。本文对节点间的依赖程度进行分析，给出节点是否归属社团的新标准。从节点强度最大的节点开始根据节点间的依赖程度寻找一个初始社团,再依据一些定量条件增加节点扩展社团，由于仅需要用到节点的局部信息，时间复杂度达到了线性。将该算法应用于经典的Zachary网络,验证了其有效性。

关键词: 复杂网络, 社团结构, 节点间的依赖程度, 定量条件, 局部算法

Abstract:

Abstract: Detecting community structure in complex networks is significant in understanding the structures and functions of networks. The dependence degree of two nodes is analyzed, and a new standard is found for whether a node is belonging to the community. An initial community is first constructed from a node with maximal node strength and its neighbors which satisfying the dependence degree quantitative condition, then the initial community is expanded by adding nodes according to some quantitative conditions. Only local information of nodes is need to use, so the time complexity is a linear complexity. It is applied to the classic Zachary network to verify the validity.

Key words:

Key words: complex network； community structures； dependence degree of two nodes； quantitative condition, local algorithm

中图分类号:

TP301.6

高洪伟1,徐勇2. 基于节点间的依赖程度划分网络中社团的算法[J]. 计算机与现代化.

GAO Hongwei1, XU Yong2. Detecting Communities of Complex Networks Based on Dependence Degree of Two Nodes[J]. Computer and Modernization.

参考文献

［1］

汪小帆,李翔,陈关荣. 复杂网络理论及其应用［M］. 北京:清华大学出版社, 2006.〖LL〗

［2］ Girvan M, Newman M E J. Community structure in social and biological networks［J］. Proc.Natl.Acad.Sci., 2002,99(12):78217826.

［3］ Ravasz E, Somera A L, Mongru D A, et al. Hierarchical organization of modularity in metabolic networks［J］. Science, 2002,297(5586):15511555.

［4］ Flake G W, Lawrence S R, Giles C L, et al. Selforganization and identification of Web communities［J］. IEEE Computer, 2002,35(3):6670.

［5］ Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs［J］. Bell Labs Technical Journal, 1970,49(2):291307.

［6］ Fiedler M. Algebraic connectivity of graphs［J］. Czechoslovak Mathematical Journal, 1973,23(2):298305.

［7］ Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs［J］. SIAM Journal on Matrix Analysis and Applications Archive, 1990,11(3):430452. 

［8］〖KG-*4〗Newman M E J. Fast algorithm for detecting community structure in networks［J］. Phys.Rev.E, 2004,69(6):15. 

［9］解,汪小帆. 复杂网络的一种快速局部社团划分算法［J］. 计算机仿真， 2007,24(11):8285.

［10］赵晓慧,刘微. 基于局部信息的复杂网络社团结构发现算法［J］. 微型机与应用, 2011，30(15):4346.

［11］Barabási A L， Albert R. Emergence of scaling in random networks［J］. Science, 1999,286(5439):509512.

［12］Wang X T, Chen G R, Lu H T. A very fast algorithm for detecting community structures in complex networks［J］. Physica A, 2007,384(2):667674.

［13］Zachary W W. An information flow model for conflict and fission in small groups［J］. Journal of Anthropological Research, 1977,33(4):452473.

[1]	张小芳, 冯慧芳. 基于轨迹大数据的动态最优路径规划[J]. 计算机与现代化, 2021, 0(11): 82-88.
[2]	李卫东, 徐澍锟, 王运明. 基于复杂网络的纽约轨道交通网络特性分析[J]. 计算机与现代化, 2021, 0(02): 94-99.
[3]	王海红, 刘莉. 基于分层和强化学习的改进路径搜索算法[J]. 计算机与现代化, 2020, 0(11): 77-82.
[4]	许小媛, 李海波, 于本成, 刘芳. 具有对偶约束的半监督重叠社区发现方法[J]. 计算机与现代化, 2020, 0(08): 63-68.
[5]	陈婧怡，徐名海，杨溪，杜帆. 一种改进的HK社交网络建模方法[J]. 计算机与现代化, 2019, 0(02): 123-.
[6]	马佳艳，王萍，夏伟，申红伟. 复杂网络下的网络流量预测和预警研究[J]. 计算机与现代化, 2018, 0(01): 102-106.
[7]	温振前，林友芳，武志昊. 基于餐饮数据复杂网络的菜品拉动力分析[J]. 计算机与现代化, 2017, 0(7): 1-9.
[8]	林家祺,卢罡,许南山. 一种基于路径阻断的求解最短路径算法[J]. 计算机与现代化, 2017, 0(12): 6-11.
[9]	周弦1,2，黄廷磊1，梁霄1. 基于社团划分的网络聚类布局算法[J]. 计算机与现代化, 2017, 0(12): 1-5+11.
[10]	陈皋，吴广潮. 基于PageRank的在线社交网络消息传播模型[J]. 计算机与现代化, 2017, 0(1): 101-105.
[11]	李甍1,2,马一方3,姜鑫1,2,马丽丽4,郑志明1,2. 一种复杂网络上信息传播的动态竞争机制[J]. 计算机与现代化, 2016, 0(1): 104-107.
[12]	王竹. 一种新型社交网络建模方法[J]. 计算机与现代化, 2015, 0(12): 57-.
[13]	樊超1，王重玺2，高鲁彬3. 政府公文收发记录的可视网络分析[J]. 计算机与现代化, 2014, 0(5): 150-155.
[14]	贾遂民，胡明生，贾志娟. 基于复杂网络的历史地震时空分布及异常分析[J]. 计算机与现代化, 2014, 0(12): 1-5.