高级搜索

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

杨书新 梁文 朱凯丽

引用本文: 杨书新, 梁文, 朱凯丽. 基于三级邻居的复杂网络节点影响力度量方法[J]. 电子与信息学报, 2020, 42(5): 1140-1148. doi: 10.11999/JEIT190440 shu
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 shu

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

    作者简介: 杨书新: 男,1979年生,副教授,研究方向为社会网络分析、生物信息学;
    梁文: 男,1994年生,硕士生,研究方向为复杂网络、计算传播学;
    朱凯丽: 女,1994年生,硕士生,研究方向为隐私保护、推荐系统
    通讯作者: 杨书新,yimuyunlang@sina.com
  • 基金项目: 国家自然科学基金(61662028),江西省教育厅科学技术研究项目基金(GJJ170518),江西省研究生创新专项资金项目(YC2018-S331)

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

English

    1. [1]

      刘阳, 季新生, 刘彩霞. 一种基于边界节点识别的复杂网络局部社区发现算法[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

    2. [2]

      田晶, 方华强, 刘佳佳, 等. 运用复杂网络方法分析城市道路网的鲁棒性[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

    3. [3]

      王凯, 刘树新, 于洪涛, 等. 基于共同邻居有效性的复杂网络链路预测算法[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

    4. [4]

      韩忠明, 刘雯, 李梦琪, 等. 基于节点向量表达的复杂网络社团划分算法[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

    5. [5]

      韩忠明, 陈炎, 李梦琪, 等. 一种有效的基于三角结构的复杂网络节点影响力度量模型[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

    6. [6]

      杨青林, 王立夫, 李欢, 等. 基于相对距离的复杂网络谱粗粒化方法[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

    7. [7]

      林冠强, 莫天文, 叶晓君, 等. 基于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

    8. [8]

      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

    9. [9]

      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.

    10. [10]

      许小可, 胡海波, 张伦, 等. 社交网络上的计算传播学[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.

    11. [11]

      陈晓龙. 社会网络影响力最大化算法及其传播模型研究[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.

    12. [12]

      王俊, 余伟, 胡亚慧, 等. 基于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

    13. [13]

      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

    14. [14]

      FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35–41. doi: 10.2307/3033543

    15. [15]

      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.

    16. [16]

      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.

    17. [17]

      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.

    18. [18]

      曹玖新, 董丹, 徐顺, 等. 一种基于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

    19. [19]

      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

    1. [1]

      宋广南, 卢海梁, 李浩, 李一楠, 郎量, 董思乔, 李鹏飞, 吕容川. 复杂天气及海风对天基被动干涉微波辐射无源探测系统性能的影响. 电子与信息学报, 2020, 42(0): 1-8.

    2. [2]

      全英汇, 高霞, 沙明辉, 陈侠达, 李亚超, 邢孟道, 岳超良. 基于期望最大化算法的捷变频联合正交频分复用雷达高速多目标参数估计. 电子与信息学报, 2020, 42(7): 1611-1618.

    3. [3]

      王粉花, 赵波, 黄超, 严由齐. 基于多尺度和注意力融合学习的行人重识别. 电子与信息学报, 2020, 42(0): 1-8.

    4. [4]

      付进, 李静, 孙思博. 平台运动对声学导航圆交汇模型的影响及误差分析. 电子与信息学报, 2020, 42(7): 1652-1660.

    5. [5]

      刘焕淋, 胡会霞, 陈勇, 温濛, 王展鹏. 节点中介性和频谱离散度感知虚拟光网络生存性协同映射. 电子与信息学报, 2020, 41(0): 1-7.

    6. [6]

      陈根华, 陈伯孝. 复杂多径信号下基于空域变换的米波雷达稳健测高算法. 电子与信息学报, 2020, 42(5): 1297-1302.

    7. [7]

      李攀攀, 谢正霞, 周志刚, 乐光学, 郑仕链, 杨小牛. 基于Hilbert填充曲线的海洋无线传感网源节点位置隐私保护方法. 电子与信息学报, 2020, 42(6): 1510-1518.

    8. [8]

      席博, 洪涛, 张更新. 卫星物联网场景下基于节点选择的协作波束成形技术研究. 电子与信息学报, 2020, 42(0): 1-9.

    9. [9]

      周牧, 李垚鲆, 谢良波, 蒲巧林, 田增山. 基于多核最大均值差异迁移学习的WLAN室内入侵检测方法. 电子与信息学报, 2020, 42(5): 1149-1157.

    10. [10]

      吕敬祥, 罗文浪. 无线传感网络量化及能量优化策略. 电子与信息学报, 2020, 42(5): 1118-1124.

    11. [11]

      刘凤增, 肖兵, 陈施思, 陈嘉勋. 负载作用下相依网络择优恢复方法研究. 电子与信息学报, 2020, 42(7): 1694-1701.

    12. [12]

      徐瑨, 吴慧慈, 陶小峰. 5G网络空间安全对抗博弈. 电子与信息学报, 2020, 41(0): 1-11.

    13. [13]

      唐伦, 魏延南, 谭颀, 唐睿, 陈前斌. H-CRAN网络下联合拥塞控制和资源分配的网络切片动态资源调度策略. 电子与信息学报, 2020, 42(5): 1244-1252.

    14. [14]

      缪祥华, 单小撤. 基于密集连接卷积神经网络的入侵检测技术研究. 电子与信息学报, 2020, 41(0): 1-7.

    15. [15]

      游凌, 李伟浩, 张文林, 王科人. 基于深度神经网络的Morse码自动译码算法. 电子与信息学报, 2020, 41(0): 1-6.

    16. [16]

      向敏, 饶华阳, 张进进, 陈梦鑫. 基于GCN的软件定义电力通信网络路由控制策略. 电子与信息学报, 2020, 42(0): 1-8.

    17. [17]

      归伟夏, 陆倩, 苏美力. 关于系统级故障诊断的烟花-反向传播神经网络算法. 电子与信息学报, 2020, 42(5): 1102-1109.

    18. [18]

      张惊雷, 厚雅伟. 基于改进循环生成式对抗网络的图像风格迁移. 电子与信息学报, 2020, 42(5): 1216-1222.

    19. [19]

      赵国繁, 唐伦, 胡彦娟, 赵培培, 陈前斌. 面向可靠性的5G网络切片重构及映射算法. 电子与信息学报, 2020, 42(6): 1478-1485.

    20. [20]

      刘文斌, 吴倩, 杜玉改, 方刚, 石晓龙, 许鹏. 基于个性化网络标志物的药物推荐方法研究. 电子与信息学报, 2020, 42(6): 1340-1347.

  • 图 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-Gnutella08CA-HepThWiKi-Vote
    节点数630198777115
    边数2077751971100762
    平均度6.5955.26428.324
    聚类系数0.0150.6000.209
    下载: 导出CSV

    表 2  精度提高比(%)

    p2p-Gnutella08Wiki-VoteCA-HepTh
    Top-1010.00133.3336.00
    Top-2022.58280.0016.46
    Top-3015.87278.695.41
    Top-402.20291.6016.09
    Top507.56272.593.32
    Top-6015.61286.5511.71
    Top-7013.77263.7810.25
    Top-809.44323.9021.49
    Top-902.71241.537.13
    Top-1001.47229.585.86
    Avg10.12260.1613.37
    下载: 导出CSV

    表 3  区分度实验结果

    方法p2p-Gnutella08WiKi-VoteCA-HepTh
    DC0.012060.042160.00557
    LTC0.050550.052050.04454
    BC0.718610.642160.40376
    LC0.851290.806890.72161
    LDDC0.607050.608990.32672
    TIM0.989050.998740.91789
    下载: 导出CSV

    表 4  运行时间 (s)

    数据集传播概率DHDD随机SCCTIMNGCCA(2)DeC
    p2p-Gnutella08p=0.0100.0220.0270.0020.0250.2580.4060.0410.046
    p=0.0200.0280.0290.0030.0360.2780.4150.0430.058
    p=0.0300.0380.0340.0050.0380.3200.4230.0450.063
    CA-HepTHp=0.0100.0140.0170.00160.0190.1940.5730.0540.030
    p=0.0250.0210.0210.00250.0270.2390.6450.0620.059
    p=0.0500.0380.0450.00620.0340.3250.7920.0760.161
    WiKi-Votep=0.0010.1410.1360.0110.1570.5171.9210.4340.412
    p=0.0050.2490.2650.0260.2610.6511.9470.4810.526
    p=0.0100.7930.7760.4800.7721.1532.4340.9751.001
    下载: 导出CSV
  • 加载中
图(7)表(5)
计量
  • PDF下载量:  31
  • 文章访问数:  1440
  • HTML全文浏览量:  325
文章相关
  • 通讯作者:  杨书新, yimuyunlang@sina.com
  • 收稿日期:  2019-06-17
  • 录用日期:  2020-02-02
  • 网络出版日期:  2020-02-20
  • 刊出日期:  2020-05-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章