Influence Maximization Algorithm Based on the Weak Tie in Social Network
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

National Science Fund for Distinguished Young Scholars of China (61225012); National Natural Science Foundation of China (61070162, 71071028, 70931001); Specialized Research Fund for the Doctoral Program of Higher Education of China (20120042130003, 20100042110025, 20110042110024); Fundamental Research Funds for the Central Universities (N110204003, N120104001)

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    This thesis introduced the solution of influence maximization and analyzed the advantages and disadvantages of those solutions. After studying the weak tie in social network, it is found that weak ties can effectively break the information barriers between different societies in social network and make information circulate in different societies. Making use of the weak tie's advantages, this thesis proposes a new solution, the BWTG algorithm, based on the greedy thought to resolve influence maximization problem. According to different solution spaces, the BWTG algorithm is divided into two different types:BCWTG and BNCWTG algorithm. There are two traditional evaluation indexes of influence maximization problem, namely, time complexity and the final activated nodes number. But considering the practical situation, a new evaluation index named ANNI is proposed to measure the ratio of profit and pay. Besides, in order to verify the performance of the proposed algorithm, different scales and types of data are used to carry out the experiment. The time complexity, the final activated nodes number and ANNI are compared with the classical Greedy algorithm. The experimental result finds that BCWTG and BNCWTG algorithm have lower time complexity and higher ANNI, but lower final activated nodes number than Greedy algorithm. But under some certain conditions, BCWTG and BNCWTG can be almost equal to Greedy in activated nodes number.

    Reference
    Related
    Cited by
Get Citation

易秀双,胡金林,王兴伟.基于社交网络弱连接属性的影响力最大化算法.软件学报,2016,27(S2):1-11

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 31,2015
  • Revised:January 05,2016
  • Adopted:
  • Online: January 10,2017
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063