高级搜索

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

杨书新 梁文 朱凯丽

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

      孙昱, 姚佩阳, 张杰勇, 付凯. 基于优化理论的复杂网络节点攻击策略. 电子与信息学报,

    2. [2]

      刘阳, 季新生, 刘彩霞. 一种基于边界节点识别的复杂网络局部社区发现算法. 电子与信息学报,

    3. [3]

      史圣卿, 陈凯, 汪玉, 罗嵘. 基于FPGA的稀疏网络关键节点计算的硬件加速方法研究. 电子与信息学报,

    4. [4]

      王凯, 刘树新, 陈鸿昶, 李星. 一种基于节点间资源承载度的链路预测方法. 电子与信息学报,

    5. [5]

      李春芳, 刘连忠, 刘振国. 数据库复杂网络构造算法及特征分析. 电子与信息学报,

    6. [6]

      李帆, 丁锦, 沈耿彪, 赵建辉. 基于复杂网络理论的编队电磁兼容网络优化. 电子与信息学报,

    7. [7]

      杜洪越, 李春双, 公利滨. 两个带有已知或未知参数的复杂网络的改进函数投影同步. 电子与信息学报,

    8. [8]

      刘树新, 季新生, 刘彩霞, 汤红波, 巩小锐. 局部拓扑信息耦合促进网络演化. 电子与信息学报,

    9. [9]

      李劲, 岳昆, 尤洁, 谢潇睿, 张云飞. 面向不确定性影响源的社会网络影响力传播抑制方法. 电子与信息学报,

    10. [10]

      邓小龙, 翟佳羽, 尹栾玉. 基于矢量影响力聚类系数的高效有向网络社团划分算法. 电子与信息学报,

    11. [11]

      王凯, 李星, 兰巨龙, 卫红权, 刘树新. 一种基于资源传输路径拓扑有效性的链路预测方法. 电子与信息学报,

    12. [12]

      刘功申, 孟魁, 郭弘毅, 苏波, 李建华. 基于贡献函数的重叠社区划分算法. 电子与信息学报,

    13. [13]

      邓志宏, 老松杨, 白亮. 基于预测误差修正的时序链路预测方法. 电子与信息学报,

    14. [14]

      郭静, 曹亚男, 周川, 张鹏, 郭莉. 基于线性阈值模型的影响力传播权重学习. 电子与信息学报,

    15. [15]

      许宇光, 潘惊治, 谢惠扬. 基于最小点覆盖和反馈点集的社交网络影响最大化算法. 电子与信息学报,

    16. [16]

      谢显中, 王闯, 雷维嘉, 兰顺福. 互信息量最大化和低复杂度的全双工中继网络自干扰消除和干扰对齐算法. 电子与信息学报,

    17. [17]

      唐伦, 张亚, 梁荣, 陈前斌. 基于网络切片的网络效用最大化虚拟资源分配算法. 电子与信息学报,

    18. [18]

      王青山, 许胤龙, 徐晨光, 张纯鹏. 无线自组网中最大化网络寿命的速率调整问题. 电子与信息学报,

    19. [19]

      王玉峰, 王文东, 程时端. 基于Stackelberg博弈的WCDMA网络收益最大化计费的研究. 电子与信息学报,

    20. [20]

      谢显中, 田瑜, 姚鑫凌, 雷维嘉. 认知网络中D2D全双工通信的速率最大化功率分配算法. 电子与信息学报,

  • 图 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.60.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  区分度实验结果

    Methodsp2p-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)

    Data setspropagation probabilityDHDDRandomSCCTIMNGCCA(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下载量:  9
  • 文章访问数:  668
  • HTML全文浏览量:  67
文章相关
  • 通讯作者:  杨书新, yimuyunlang@sina.com
  • 收稿日期:  2019-06-17
  • 录用日期:  2020-02-02
  • 网络出版日期:  2020-02-20
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章