A Genetic NewGreedy Algorithm for Influence Maximization in Social Network

被引：28

作者：

Tsai, Chun-Wei ^{[1
]}

Yang, Yo-Chung ^{[2
]}

Chiang, Ming-Chao ^{[2
]}

机构：

[1] Natl Ilan Univ, Dept Comp Sci & Informat Engn, Yilan 26047, Taiwan

[2] Natl Sun Yat Sen Univ, Dept Comp Sci & Engn, Kaohsiung 80424, Taiwan

来源：

2015 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC 2015): BIG DATA ANALYTICS FOR HUMAN-CENTRIC SYSTEMS | 2015年

关键词：

Genetic algorithm; social network; influence maximization;

D O I：

10.1109/SMC.2015.446

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A user may be influenced by the other users of a social network by sharing information. Influence maximization is one of the critical research topics aimed at knowing the current circumstances of a social network, such as the general mood of the society. The goal of this problem is to find a seed set which has a maximum influence with respect to a propagation model. For the influence maximization problem is NP-Hard, it is obvious that an exhausted search algorithm is not able to find the solution in a reasonable time. It is also obvious that a greedy algorithm may not find a solution that satisfies all the requirements. Hence, a high-performance algorithm for solving the influence maximization problem, which leverages the strength of the greedy method and the genetic algorithm (GA) is presented in this paper. Experimental results show that the proposed algorithm can provide a better result than simple GA by about 10% in terms of the quality.

引用

页码：2549 / 2554

页数：6

共 15 条

[1]

Aggarwal CC, 2011, SOCIAL NETWORK DATA ANALYTICS, P353

[2]

Aggarwal CC, 2011, SOCIAL NETWORK DATA ANALYTICS, P1

[3]

[Anonymous], NATL ACAD SCI

[4]

[Anonymous], P ANN C GEN EV COMP

[5]

[Anonymous], CO INFO FAC NEWSR

[6]

[Anonymous], COMPUTATIONAL INFORM

[7]

Bhagat S, 2011, SOCIAL NETWORK DATA ANALYTICS, P115

[8] Efficient Influence Maximization in Social Networks [J].

Chen, Wei ;

Wang, Yajun ;

Yang, Siyu .

KDD-09: 15TH ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, 2009, :199-207

[9]

Chen Wei., 2010, Proceedings of the ACM SIGKDD International Conference on Knowledge discovery and data mining, P1029, DOI DOI 10.1145/1835804.1835934

[10] A Data-Based Approach to Social Influence Maximization [J].

Goyal, Amit ;

Bonchi, Francesco ;

Lakshmanan, Laks V. S. .

PROCEEDINGS OF THE VLDB ENDOWMENT, 2011, 5 (01) :73-84

← 1 2 →