寻找复杂网络社团的稠密集算法

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

寻找复杂网络社团的稠密集算法

谢福鼎, 张大为, 黄丹, 张永, 孙岩

文章导航 > 电子科技大学学报 > 2011 > 40(4): 483-490

谢福鼎, 张大为, 黄丹, 张永, 孙岩. 寻找复杂网络社团的稠密集算法[J]. 电子科技大学学报, 2011, 40(4): 483-490. doi: 10.3969/j.issn.1001-0548.2011.04.001

引用本文:

谢福鼎, 张大为, 黄丹, 张永, 孙岩. 寻找复杂网络社团的稠密集算法[J]. 电子科技大学学报, 2011, 40(4): 483-490. doi: 10.3969/j.issn.1001-0548.2011.04.001

XIE Fu-ding, ZHANG Da-wei, HUANG Dan, ZHANG Yong, SUN Yan. Density Set Algorithm Search for Communities in Complex Networks[J]. Journal of University of Electronic Science and Technology of China, 2011, 40(4): 483-490. doi: 10.3969/j.issn.1001-0548.2011.04.001

Citation:

XIE Fu-ding, ZHANG Da-wei, HUANG Dan, ZHANG Yong, SUN Yan. Density Set Algorithm Search for Communities in Complex Networks[J]. Journal of University of Electronic Science and Technology of China, 2011, 40(4): 483-490. doi: 10.3969/j.issn.1001-0548.2011.04.001

寻找复杂网络社团的稠密集算法

doi: 10.3969/j.issn.1001-0548.2011.04.001

1.
辽宁师范大学城市与环境科学学院辽宁大连 116029;
2.
辽宁师范大学计算机与信息技术学院辽宁大连 116081

基金项目:

国家自然科学基金(10771092)

作者简介:
谢福鼎(1965-)，男，博士，教授，主要从事人工智能、数据挖掘及计算机代数方面的研究.

中图分类号: TP301.6

Density Set Algorithm Search for Communities in Complex Networks

1.
College of Urban and Environmental Sciences,Liaoning Normal University Dalian Liaoning 116029;
2.
Department of Computer Science,Liaoning Normal University Dalian Liaoning 116081

Funds:

Supported by the National Natural Science Foundation of China under Grant(10771092)

摘要: 通过引入稠密集的概念，该文提出了一种基于稠密集的寻找复杂网络中社团结构的算法。算法的主要思想是在网络中不断构造稠密集，并判断后生成的稠密集能否导致产生一个新社团，还是将其与一个已有的社团合并。利用该算法可以将具有明显社团结构的网络进行比较合理的划分。在一般情况下，该算法的时间复杂度约为O(n+m)，对于稀疏网络的时间复杂度约为O(n)，其中n为网络的节点数，m为边数。对3个典型实际网络和一个标准测试网络的试验结果表明，该方法获得了理想的社团结构划分。该方法在计算机、物理及其他学科领域具有广泛的应用前景。
- 复杂网络 /
- 社团结构 /
- 稠密集
Abstract: To detect communities in complex networks, a density set algorithm (DSA) is proposed by introducing the concept of density set. The key idea of the algorithm is to constantly construct density sets in a network and decide whether the density set founded later can lead to generate a new community or amalgamate it with an old one. Step by step, the networks with apparent community structure can be partitioned well by the proposed method. The running time of DSA is approximately O(n+m) for a general network and O(n) for a sparse network, where n is the number of nodes and m the number of edges in a network. Tests on three typical real world networks and a benchmark reveal that DSA produces desired results. So the proposal is reasonable, and has the potential for wide applications in physics and computer science.
- complex network /
- community /
- density set

[1]	邢玲, 邓凯凯, 吴红海, 谢萍. 复杂网络视角下跨社交网络用户身份识别研究综述 . 电子科技大学学报, 2020, 49(6): 905-917. doi: 10.12178/1001-0548.2019182
[2]	邵鹏, 胡平. 复杂网络特殊用户对群体观点演化的影响 . 电子科技大学学报, 2019, 48(4): 604-612. doi: 10.3969/j.issn.1001-0548.2019.04.019
[3]	孙晓璇, 吴晔, 冯鑫, 肖井华. 高铁-普铁的实证双层网络结构与鲁棒性分析 . 电子科技大学学报, 2019, 48(2): 315-320. doi: 10.3969/j.issn.1001-0548.2019.02.024
[4]	赵紫娟, 李小珂, 郭强, 杨凯, 刘建国. 基于LDA的复杂网络整体研究态势主题分析 . 电子科技大学学报, 2019, 48(6): 931-938. doi: 10.3969/j.issn.1001-0548.2019.06.019
[5]	吴宗柠, 樊瑛. 复杂网络视角下国际贸易研究综述 . 电子科技大学学报, 2018, 47(3): 469-480. doi: 10.3969/j.issn.1001-0548.2018.03.023
[6]	顾亦然, 朱梓嫣. 基于LeaderRank和节点相似度的复杂网络重要节点排序算法 . 电子科技大学学报, 2017, 46(2): 441-448. doi: 10.3969/j.issn.1001-0548.2017.02.020
[7]	杨凯, 郭强, 刘晓露, 刘建国. 基于多重特征向量的有向网络社团结构划分算法 . 电子科技大学学报, 2016, 45(6): 1014-1019, 1032. doi: 10.3969/j.issn.1001-0548.2016.06.024
[8]	苟智坚, 范明钰, 王光卫. 复杂网络中无信任边界限制的连续观点演化研究 . 电子科技大学学报, 2015, 44(5): 749-756. doi: 10.3969/j.issn.1001-0548.2015.05.019
[9]	尚可可, 许小可. 基于置乱算法的复杂网络零模型构造及其应用 . 电子科技大学学报, 2014, 43(1): 7-20. doi: 10.3969/j.issn.1001-0548.2014.01.002
[10]	汤蓉, 唐常杰, 徐开阔, 杨宁. 基于局部聚合的复杂网络自动聚簇算法 . 电子科技大学学报, 2014, 43(3): 329-335. doi: 10.3969/j.issn.1001-0548.2014.03.002
[11]	周涛, 张子柯, 陈关荣, 汪小帆, 史定华, 狄增如, 樊瑛, 方锦清, 韩筱璞, 刘建国, 刘润然, 刘宗华, 陆君安, 吕金虎, 吕琳媛, 荣智海, 汪秉宏, 许小可, 章忠志. 复杂网络研究的机遇与挑战 . 电子科技大学学报, 2014, 43(1): 1-5. doi: 10.3969/j.issn.1001-0548.2014.01.001
[12]	唐雪飞, 杨陈皓, 牛新征. 复杂网络链路危险度预测模型研究 . 电子科技大学学报, 2013, 42(3): 442-447. doi: 10.3969/j.issn.1001-0548.2013.03.024
[13]	王伟, 杨慧, 龚凯, 唐明, 都永海. 复杂网络上的局域免疫研究 . 电子科技大学学报, 2013, 42(6): 817-830.
[14]	张昌利, 龚建国, 闫茂德. 基于复杂网络的社会化标签语义相似度分析 . 电子科技大学学报, 2012, 41(5): 642-648. doi: 10.3969/j.issn.1001-0548.2012.05.001
[15]	陈娟, 陆君安. 复杂网络中尺度研究揭开网络同步化过程 . 电子科技大学学报, 2012, 41(1): 8-16. doi: 10.3969/j.issn.1001-0548.2012.01.002
[16]	张聪, 沈惠璋. 网络自然密度社团结构模块度函数 . 电子科技大学学报, 2012, 41(2): 185-191. doi: 10.3969/j.issn.1001-0548.2012.02.003
[17]	张昊, 陈超, 王长春. 基于空穴理论的复杂网络传染病传播控制 . 电子科技大学学报, 2011, 40(4): 491-496.
[18]	朱大勇, 张新丽, 李树全. 利用局部拓扑信息发现模糊社团结构 . 电子科技大学学报, 2011, 40(1): 73-79. doi: 10.3969/j.issn.1001-0548.2011.01.014
[19]	吕琳媛. 复杂网络链路预测 . 电子科技大学学报, 2010, 39(5): 651-661. doi: 10.3969/j.issn.1001-0548.2010.05.002
[20]	汪小帆, 刘亚冰. 复杂网络中的社团结构算法综述 . 电子科技大学学报, 2009, 38(5): 537-543. doi: 10.3969/j.issn.1001-0548.2009.05.007

WeChat

点击查看大图

计量

文章访问数: 3702
HTML全文浏览量: 168
PDF下载量: 62
被引次数: 0

寻找复杂网络社团的稠密集算法

doi: 10.3969/j.issn.1001-0548.2011.04.001

1. 辽宁师范大学城市与环境科学学院辽宁大连 116029;

2. 辽宁师范大学计算机与信息技术学院辽宁大连 116081

基金项目:

国家自然科学基金(10771092)

作者简介:
谢福鼎(1965-)，男，博士，教授，主要从事人工智能、数据挖掘及计算机代数方面的研究.

收稿日期: 2011-06-15
刊出日期: 2011-08-15

中图分类号: TP301.6

关键词:

摘要: 通过引入稠密集的概念，该文提出了一种基于稠密集的寻找复杂网络中社团结构的算法。算法的主要思想是在网络中不断构造稠密集，并判断后生成的稠密集能否导致产生一个新社团，还是将其与一个已有的社团合并。利用该算法可以将具有明显社团结构的网络进行比较合理的划分。在一般情况下，该算法的时间复杂度约为O(n+m)，对于稀疏网络的时间复杂度约为O(n)，其中n为网络的节点数，m为边数。对3个典型实际网络和一个标准测试网络的试验结果表明，该方法获得了理想的社团结构划分。该方法在计算机、物理及其他学科领域具有广泛的应用前景。

English Abstract

谢福鼎, 张大为, 黄丹, 张永, 孙岩. 寻找复杂网络社团的稠密集算法[J]. 电子科技大学学报, 2011, 40(4): 483-490. doi: 10.3969/j.issn.1001-0548.2011.04.001

引用本文:

谢福鼎, 张大为, 黄丹, 张永, 孙岩. 寻找复杂网络社团的稠密集算法[J]. 电子科技大学学报, 2011, 40(4): 483-490. doi: 10.3969/j.issn.1001-0548.2011.04.001

XIE Fu-ding, ZHANG Da-wei, HUANG Dan, ZHANG Yong, SUN Yan. Density Set Algorithm Search for Communities in Complex Networks[J]. Journal of University of Electronic Science and Technology of China, 2011, 40(4): 483-490. doi: 10.3969/j.issn.1001-0548.2011.04.001

Citation:

XIE Fu-ding, ZHANG Da-wei, HUANG Dan, ZHANG Yong, SUN Yan. Density Set Algorithm Search for Communities in Complex Networks[J]. Journal of University of Electronic Science and Technology of China, 2011, 40(4): 483-490. doi: 10.3969/j.issn.1001-0548.2011.04.001

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发