高级搜索

留言板

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

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

基于三级邻居的复杂网络节点影响力度量方法

杨书新 梁文 朱凯丽

杨书新, 梁文, 朱凯丽. 基于三级邻居的复杂网络节点影响力度量方法[J]. 电子与信息学报, 2020, 42(5): 1140-1148. doi: 10.11999/JEIT190440
引用本文: 杨书新, 梁文, 朱凯丽. 基于三级邻居的复杂网络节点影响力度量方法[J]. 电子与信息学报, 2020, 42(5): 1140-1148. doi: 10.11999/JEIT190440
Shuxin YANG, Wen LIANG, Kaili ZHU. Measurement of Node Influence Based on Three-level Neighbor in Complex Networks[J]. Journal of Electronics and Information Technology, 2020, 42(5): 1140-1148. doi: 10.11999/JEIT190440
Citation: Shuxin YANG, Wen LIANG, Kaili ZHU. Measurement of Node Influence Based on Three-level Neighbor in Complex Networks[J]. Journal of Electronics and Information Technology, 2020, 42(5): 1140-1148. doi: 10.11999/JEIT190440

基于三级邻居的复杂网络节点影响力度量方法

doi: 10.11999/JEIT190440
基金项目: 国家自然科学基金(61662028),江西省教育厅科学技术研究项目基金(GJJ170518),江西省研究生创新专项资金项目(YC2018-S331)
详细信息
    作者简介:

    杨书新:男,1979年生,副教授,研究方向为社会网络分析、生物信息学

    梁文:男,1994年生,硕士生,研究方向为复杂网络、计算传播学

    朱凯丽:女,1994年生,硕士生,研究方向为隐私保护、推荐系统

    通讯作者:

    杨书新  yimuyunlang@sina.com

  • 中图分类号: TP39

Measurement of Node Influence Based on Three-level Neighbor in Complex Networks

Funds: The National Natural Science Foundation of China (61662028), The Scientific Technology Research Foundation of the Education Department of Jiangxi Province (GJJ170518), The Special Foundation of Postgraduate Innovation of Jiangxi province (YC2018-S331)
  • 摘要:

    已有的节点影响力度量方法均存在一定的局限性。该文基于三度影响力原则,综合考虑局部度量的适宜层次及大规模网络的可扩展性,提出一种基于3级邻居的节点影响力度量方法(TIM)。该方法将节点2, 3级具有传播衰减特性的邻居视为整体,用于度量节点的影响能力。利用传染病模型及独立级联模型,在3个真实数据集验证了该方法的有效性。实验结果表明,基于3级邻居的节点影响力度量方法在影响力一致性、区分度、排序性等指标中表现优越,且能够有效求解影响力最大化问题。

  • 图  1  3级影响传播示例

    图  2  参数 $R\left( \theta \right)$ 对应的直方图

    图  3  影响力一致性实验结果

    图  4  排序性能

    图  5  p2p-Gnutella08数据集实验结果

    图  6  CA-HepTH数据集实验结果

    图  7  WiKi-Vote数据集

     算法1 TIM度量方法
     输入: G=(V, E, P) /*P 表示传播概率*/
     输出: 每个节点的TIM度量值
     (1) function: F(·) /*1级邻居的层序遍历函数*/
     (2) for each u in V do
     (3) TIM(u) = 0, x=0, l=0 /*l 为集合的长度*/
     (4) for each v in F(u) do:
     (5) x += p(u, v)
     (6) end for
     (7) TIM(u) = $\theta \cdot $ exp(x)
     (8) for each v in F(u) do:
     (9) for each w in F(v) \{u} do:
     (10) l=getSize ( {F(w) , w } \{ F(u)})
     (11) TIM(u) += p(u, v) × p(v, w) × l
     (12) end for
     (13) end for
     (14) end for
    下载: 导出CSV

    表  1  网络数据集基本特征

    p2p-Gnutella08 CA-HepTh WiKi-Vote
    节点数 6301 9877 7115
    边数 20777 51971 100762
    平均度 6.595 5.264 28.324
    聚类系数 0.015 0.600 0.209
    下载: 导出CSV

    表  2  精度提高比(%)

    p2p-Gnutella08 Wiki-Vote CA-HepTh
    Top-10 10.00 133.33 36.00
    Top-20 22.58 280.00 16.46
    Top-30 15.87 278.69 5.41
    Top-40 2.20 291.60 16.09
    Top50 7.56 272.59 3.32
    Top-60 15.61 286.55 11.71
    Top-70 13.77 263.78 10.25
    Top-80 9.44 323.90 21.49
    Top-90 2.71 241.53 7.13
    Top-100 1.47 229.58 5.86
    Avg 10.12 260.16 13.37
    下载: 导出CSV

    表  3  区分度实验结果

    方法 p2p-Gnutella08 WiKi-Vote CA-HepTh
    DC 0.01206 0.04216 0.00557
    LTC 0.05055 0.05205 0.04454
    BC 0.71861 0.64216 0.40376
    LC 0.85129 0.80689 0.72161
    LDDC 0.60705 0.60899 0.32672
    TIM 0.98905 0.99874 0.91789
    下载: 导出CSV

    表  4  运行时间 (s)

    数据集 传播概率 DH DD 随机 SCC TIM NG CCA(2) DeC
    p2p-Gnutella08 p=0.010 0.022 0.027 0.002 0.025 0.258 0.406 0.041 0.046
    p=0.020 0.028 0.029 0.003 0.036 0.278 0.415 0.043 0.058
    p=0.030 0.038 0.034 0.005 0.038 0.320 0.423 0.045 0.063
    CA-HepTH p=0.010 0.014 0.017 0.0016 0.019 0.194 0.573 0.054 0.030
    p=0.025 0.021 0.021 0.0025 0.027 0.239 0.645 0.062 0.059
    p=0.050 0.038 0.045 0.0062 0.034 0.325 0.792 0.076 0.161
    WiKi-Vote p=0.001 0.141 0.136 0.011 0.157 0.517 1.921 0.434 0.412
    p=0.005 0.249 0.265 0.026 0.261 0.651 1.947 0.481 0.526
    p=0.010 0.793 0.776 0.480 0.772 1.153 2.434 0.975 1.001
    下载: 导出CSV
  • 刘阳, 季新生, 刘彩霞. 一种基于边界节点识别的复杂网络局部社区发现算法[J]. 电子与信息学报, 2014, 36(12): 2809–2815. doi: 10.3724/SP.J.1146.2013.01955

    LIU Yang, JI Xinsheng, and LIU Caixia. Detecting local community structure based on the identification of boundary nodes in complex networks[J]. Journal of Electronics&Information Technology, 2014, 36(12): 2809–2815. doi: 10.3724/SP.J.1146.2013.01955
    田晶, 方华强, 刘佳佳, 等. 运用复杂网络方法分析城市道路网的鲁棒性[J]. 武汉大学学报: 信息科学版, 2019, 44(5): 771–777. doi: 10.13203/j.whugis20150334

    TIAN Jing, FANG Huaqiang, LIU Jiajia, et al. Robustness analysis of urban street networks using complex network method[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 771–777. doi: 10.13203/j.whugis20150334
    王凯, 刘树新, 于洪涛, 等. 基于共同邻居有效性的复杂网络链路预测算法[J]. 电子科技大学学报, 2019, 48(3): 432–439. doi: 10.3969/j.issn.1001-0548.2019.03.020

    WANG Kai, LIU Shuxin, YU Hongtao, et al. Predicting missing links of complex network via effective common neighbors[J]. Journal of University of Electronic Science and Technology of China, 2019, 48(3): 432–439. doi: 10.3969/j.issn.1001-0548.2019.03.020
    韩忠明, 刘雯, 李梦琪, 等. 基于节点向量表达的复杂网络社团划分算法[J]. 软件学报, 2019, 30(4): 1045–1061. doi: 10.13328/j.cnki.jos.005387

    HAN Zhongming, LIU Wen, LI Mengqi, et al. Community detection algorithm based on node embedding vector representation[J]. Journal of Software, 2019, 30(4): 1045–1061. doi: 10.13328/j.cnki.jos.005387
    韩忠明, 陈炎, 李梦琪, 等. 一种有效的基于三角结构的复杂网络节点影响力度量模型[J]. 物理学报, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901

    HAN Zhongming, CHEN Yan, LI Mengqi, et al. An efficient node influence metric based on triangle in complex networks[J]. Acta Physica Sinica, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
    杨青林, 王立夫, 李欢, 等. 基于相对距离的复杂网络谱粗粒化方法[J]. 物理学报, 2019, 68(10): 100501. doi: 10.7498/aps.68.20181848

    YANG Qinglin, WANG Lifu, LI Huan, et al. A spectral coarse graining algorithm based on relative distance[J]. Acta Physica Sinica, 2019, 68(10): 100501. doi: 10.7498/aps.68.20181848
    林冠强, 莫天文, 叶晓君, 等. 基于TOPSIS和CRITIC法的电网关键节点识别[J]. 高电压技术, 2018, 44(10): 3383–3389. doi: 10.13336/j.1003-6520.hve.20180925030

    LIN Guanqiang, MO Tianwen, YE Xiaojun, et al. Critical node identification of power networks based on TOPSIS and CRITIC methods[J]. High Voltage Engineering, 2018, 44(10): 3383–3389. doi: 10.13336/j.1003-6520.hve.20180925030
    CHRISTAKIS N A and FOWLER J H. Social contagion theory: Examining dynamic social networks and human behavior[J]. Statistics in Medicine, 2013, 32(4): 556–577. doi: 10.1002/sim.5408
    CHRISTAKIS N A and FOWLER J H. Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives[M]. New York: Little, Brown and Company, 2009: 30–117.
    许小可, 胡海波, 张伦, 等. 社交网络上的计算传播学[M]. 北京: 高等教育出版社, 2015: 163–198.

    XU Xiaoke, HU Haibo, ZHANG Lun, et al. Computational Communication in Social Networks[M]. Beijing: Higher Education Press, 2015: 163–198.
    陈晓龙. 社会网络影响力最大化算法及其传播模型研究[D]. [硕士论文], 哈尔滨工程大学, 2016: 20–22.

    CHEN Xiaolong. Research on influence maximization and diffusion model in social networks[D]. [Master dissertation], Harbin Engineering University, 2016: 20–22.
    王俊, 余伟, 胡亚慧, 等. 基于3-layer中心度的社交网络影响力最大化算法[J]. 计算机科学, 2014, 41(1): 59–63. doi: 10.3969/j.issn.1002-137X.2014.01.009

    WANG Jun, XU Wei, HU Yahui, et al. Heuristic algorithm based on 3-layer centrality for influence maximization in social networks[J]. Computer Science, 2014, 41(1): 59–63. doi: 10.3969/j.issn.1002-137X.2014.01.009
    CHEN Duanbing, LÜ Linyuan, SHANG Mingsheng, et al. Identifying influential nodes in complex networks[J]. Physica A:Statistical Mechanics and its Applications, 2012, 391(4): 1777–1787. doi: 10.1016/j.physa.2011.09.017
    FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35–41. doi: 10.2307/3033543
    LI Jianxin, LIU Chengfei, XU J X, et al. Personalized influential topic search via social network summarization[C]. The 33rd IEEE International Conference on Data Engineering, San Diego, USA, 2016: 1820–1834. doi: 10.1109/ICDE.2017.15.
    CHEN Wei, WANG Yajun, and YANG Siyu. Efficient influence maximization in social networks[C]. The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009: 199–208. doi: 10.1145/1557019.1557047.
    KEMPE D, KLEINBERG J, and TARDOS É. Maximizing the spread of influence through a social network[C]. The 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA, 2003: 137–146. doi: 10.1145/956750.956769.
    曹玖新, 董丹, 徐顺, 等. 一种基于k-核的社会网络影响最大化算法[J]. 计算机学报, 2015, 38(2): 238–248. doi: 10.3724/SP.J.1016.2015.00238

    CAO Jiuxin, DONG Dan, XU Shun, et al. A k-core based algorithm for influence maximization in social networks[J]. Chinese Journal of Computers, 2015, 38(2): 238–248. doi: 10.3724/SP.J.1016.2015.00238
    IBNOULOUAFI A and EL HAZITI M. Density centrality: Identifying influential nodes based on area density formula[J]. Chaos,Solitons&Fractals, 2018, 114: 69–80. doi: 10.1016/j.chaos.2018.06.022
  • 加载中
图(7) / 表(5)
计量
  • 文章访问数:  1833
  • HTML全文浏览量:  508
  • PDF下载量:  53
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-06-17
  • 修回日期:  2020-02-02
  • 网络出版日期:  2020-02-20
  • 刊出日期:  2020-06-04

目录

    /

    返回文章
    返回

    官方微信,欢迎关注