高级搜索

基于最小点覆盖和反馈点集的社交网络影响最大化算法

许宇光 潘惊治 谢惠扬

引用本文: 许宇光, 潘惊治, 谢惠扬. 基于最小点覆盖和反馈点集的社交网络影响最大化算法[J]. 电子与信息学报, 2016, 38(4): 795-802. doi: 10.11999/IEIT160019 shu
Citation:  XU Yuguang, PAN Jingzhi, XIE Huiyang. Minimum Vertex Covering and Feedback Vertex Set-based Algorithm for Influence Maximization in Social Network[J]. Journal of Electronics and Information Technology, 2016, 38(4): 795-802. doi: 10.11999/IEIT160019 shu

基于最小点覆盖和反馈点集的社交网络影响最大化算法

摘要: 社交网络中的影响最大化问题是指在特定的传播模型下,如何寻找k个最具影响力的节点使得在该模型下社交网络中被影响的节点最多,信息传播的范围最广。该问题是一个优化问题,并且已经被证明是NP-难的。考虑到图的最小点覆盖和反馈点集中的顶点对图的连通性影响较大,该文提出一种基于最小点覆盖和反馈点集的社交网络影响最大化算法(Minimum Vertex Covering and Feedback Vertex Set, MVCFVS),并给出了具体的仿真实验和分析。实验结果表明,与最新的算法比较,该算法得到的节点集在多种模型下都具有优异的传播效果,例如在独立级联模型和加权级联模型中超过当前最好的算法,并且还具有更快的收敛速度。

English

    1. [1]

      WATTS D J and STROGATZ S H. Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393(6684): 440-442.

    2. [2]

      BARABASI A L and ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

    3. [3]

      SAITO K, NAKANA R, and KIMURA M. Prediction of information diffusion probabilities for independent cascade model[J]. Lecture Notes in Computer Science, 2008, 5179: 67-75.

    4. [4]

      TANG J, SUN J, and YANG Z. Social influence analysis in large-scale networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, 2009: 807-816.

    5. [5]

      GOYAL A, BONCHI F, and LASKHMANAN L. Learning influence probabilities in social networks[C]. Proceedings of the Third ACM International Conference on Web Search Data Mining, New York, USA, 2010: 241-250.

    6. [6]

      WANG C, TANG J, SUN J, et al. Dynamic social influence analysis through time-dependent factor graphs[C]. Proceedings of the 2011 International Conference on Advances in Social Networks Analysis and Mining, Washington, DC, USA, 2011: 239-246.

    7. [7]

      DOMIGOS P and RICHARDSON M. Mining the network value of customers[C]. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, USA, 2001: 57-66.

    8. [8]

      RICHARDSON M and DOMINGOS P. Mining knowledge- sharing sites for viral marketing[C]. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Alberta, Canada, 2002: 61-70.

    9. [9]

      KEMPE D, KLEINBERG J, and TARDOS E. Influential nodes in a diffusion model for social networks[J]. International Colloquium on Automata, Languages and Programming, 2005, 32: 1127-1138.

    10. [10]

      KEMPE D, KLEINBERG J, and TARDOS E. Maximizing the spread of influence in a social network[C]. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA, 2003: 137-146.

    11. [11]

      LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost- effective outbreak detection in networks[C]. Proceedings of the Kdd 07 ACM SIGKDD International Conference on Knowledge Discovery and Data, Pittsburgh, PA, USA, 2007: 420-429.

    12. [12]

      ZHOU C and GUO L. A note on influence maximization in social networks from local to global and beyond[C]. Proceedings of the 1th International Conference on Data Science (ICDS), Beijing, China, 2014: 27-28.

    13. [13]

      ZHOU C, ZHANG P, GUO J, et al. An upper bound based greedy algorithm for mining top-k influential nodes in social networks [C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data, Seoul, Korea, 2014: 421-422.

    14. [14]

      CHENG S, SHEN H, HUANG J, et al. IMRank: influence maximization via finding self-consistent ranking[C]. Proceedings of the 37th International ACM SIGIR Conference on Research Development in Information Retrieval?(SIGIR '14), New York, NY, USA, 2014: 475-484.

    15. [15]

      CHEN W, WANG Y, and YANG S. Efficient influence maximization in social networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009: 199-208.

    16. [16]

      JIANG Q, SONG G, CONG G, et al. Simulated annealing based influence maximization in social networks[C]. Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 2011: 127-132.

    17. [17]

      ZOU F, ZHANG Z, and WU W. Latency-bounded minimum influential node selection in social networks[C]. Proceedings of the Wireless Algorithms, Systems, and Applications, 4th International Conference, Boston, MA, USA, 2009: 519-526.

    18. [18]

      ZOU F, WILLSON J, ZHANG Z, et al. Fast information propagation in social networks[J]. Discrete Mathematics Algorithms Applications, 2010, 2(1): 125-141.

    19. [19]

      COHEN E, DELLING D, PAJOR T, et al. Sketch-based influence maximization and computation: scaling up with guarantees[C]. Proceedings of Conference on Information and Knowledge Management, CIKM, Shanghai, China, 2014: 629-638.

    20. [20]

      JIANG F, JIN S, WU Y, et al. A uniform framework for community detection via influence maximization in social networks[C]. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Beijing, China, 2014: 27-32.

    21. [21]

      CAO J, DAN D, XU S, et al. A k-core based algorithm for influence maximization in social networks[J]. Chinese Journal of Computers, 2015, 38(2): 238-248.

    22. [22]

      LUCIER B, OREN J, and SINGER Y. Singer influence at scale: distributed computation of complex contagion in networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, 2015: 735-744.

    23. [23]

      GOLDENBERG J, LIBAI B, and MULLER E. Talk of the network: a complex systems look at the underlying process of word-of-mouth [J]. Marketing Letters, 2001, 12(3): 211-223.

    24. [24]

      KARP R M. Reducibility among Combinatorial Problems, Complexity of Computer Computations[M]. New York, USA, Plenum Press, 1972: 85-103.

    25. [25]

      SCHULZ A. Correctness-proof of a greedy-algorithm for minimum vertex cover of a tree[OL]. http.//cs.stakexchange. com, 2013.

    26. [26]

      LESKOVEC J, KLEINBERG J, and FALOUTSOS C. Graph evolution: densification and shrink diameters[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 1-41.

    27. [27]

      LESKOVEC J, LANG K, DASGUPTA A, et al. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1): 29-123.

    28. [28]

      MCAULEY J and LESKOVEC J. Learning to discover social circles in ego networks[C]. Proceedings of the 26th Annal Conference on Information Processing Systems, Lake Tahoe, NeVada, USA, 2012: 539-547.

    1. [1]

      熊余, 董先存, 李圆圆, 吕翊, 王汝言. 软件定义光网络中基于最小点覆盖的控制平面跨层生存性设计. 电子与信息学报, 2016, 38(5): 1211-1218.

    2. [2]

      肖云鹏, 杨光, 刘宴兵, 吴斌. 一种基于最大熵原理的社交网络用户关系分析模型. 电子与信息学报, 2017, 39(4): 778-784.

    3. [3]

      胡长军, 许文文, 胡颖, 方明哲, 刘峰. 在线社交网络信息传播研究综述. 电子与信息学报, 2017, 39(4): 794-804.

    4. [4]

      黄宏程, 赖礼城, 胡敏, 孙欣然, 陶洋. 基于严格可控理论的社交网络信息传播控制方法. 电子与信息学报, 2018, 40(7): 1707-1714.

    5. [5]

      姬建睿, 刘业政, 姜元春. 基于混合权重合并策略的社交网络用户关注点识别方法. 电子与信息学报, 2017, 39(9): 2056-2062.

    6. [6]

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

    7. [7]

      刘宇, 吴斌, 曾雪琳, 张云雷, 王柏. 一种基于社交网络社区的组推荐框架. 电子与信息学报, 2016, 38(9): 2150-2157.

    8. [8]

      吴大鹏, 司书山, 闫俊杰, 王汝言. 基于行为特征分析的社交网络女巫节点检测机制. 电子与信息学报, 2017, 39(9): 2089-2096.

    9. [9]

      陈鸿昶, 徐乾, 黄瑞阳, 程晓涛, 吴铮. 一种基于用户轨迹的跨社交网络用户身份识别算法. 电子与信息学报, 2018, 40(11): 2758-2764.

    10. [10]

      陈季梦, 陈佳俊, 刘杰, 黄亚楼, 王嫄, 冯霞. 基于结构相似度的大规模社交网络聚类算法. 电子与信息学报, 2015, 37(2): 449-454.

    11. [11]

      徐少毅, 张鹏. D2D协作通信网络中基于社交信息的中继选择和功率分配. 电子与信息学报, 2017, 39(5): 1142-1149.

    12. [12]

      李磊, 楚喻棋, 汪萌, 韩莉, 吴信东. 基于NSGA2的网络环境下多标签种子节点选择. 电子与信息学报, 2017, 39(9): 2040-2047.

    13. [13]

      刘嘉琪, 齐佳音. 基于社会系统响应函数的在线群体分类研究. 电子与信息学报, 2016, 38(9): 2141-2149.

    14. [14]

      胡颖, 胡长军, 傅树深, 黄建一. 流行度演化分析与预测综述. 电子与信息学报, 2017, 39(4): 805-816.

    15. [15]

      孙晓, 彭晓琪, 胡敏, 任福继. 基于多维扩展特征与深度学习的微博短文本情感分析. 电子与信息学报, 2017, 39(9): 2048-2055.

    16. [16]

      汪晓锋, 刘功申, 李建华. 基于模糊聚类的多分辨率社区发现方法. 电子与信息学报, 2017, 39(9): 2033-2039.

    17. [17]

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

    18. [18]

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

    19. [19]

      王玉峰, 王文东, 程时端. 基于Stackelberg博弈的WCDMA网络收益最大化计费的研究. 电子与信息学报, 2005, 27(9): 1488-1492.

    20. [20]

      张雷, 武刚, 李少谦. 有限反馈MISO-OFDM系统中最大化容量的波束成形. 电子与信息学报, 2009, 31(7): 1542-1547.

  • 加载中
计量
  • PDF下载量:  750
  • 文章访问数:  513
  • HTML全文浏览量:  20
文章相关
  • 收稿日期:  2016-01-05
  • 录用日期:  2016-02-26
  • 刊出日期:  2016-04-19
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章