DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks

Cui, L; Hu, H; Yu, S; Yan, Q; Ming, Z; Wen, Z; Lu, N

DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks

Cui, L Hu, H Yu, S

Yan, Q Ming, Z Wen, Z Lu, N

Permalink

Publisher:: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Publication Type:: Journal Article
Citation:: Journal of Network and Computer Applications, 2018, 103, pp. 119-130
Issue Date:: 2018-02-01

Closed Access

	Filename	Description	Size
	DDSE.pdf	Published version	1.24 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Cui, L
dc.contributor.author	Hu, H
dc.contributor.author	Yu, S https://orcid.org/0000-0003-4485-6743
dc.contributor.author	Yan, Q
dc.contributor.author	Ming, Z
dc.contributor.author	Wen, Z
dc.contributor.author	Lu, N
dc.date.accessioned	2021-04-29T00:18:24Z
dc.date.available	2021-04-29T00:18:24Z
dc.date.issued	2018-02-01
dc.identifier.citation	Journal of Network and Computer Applications, 2018, 103, pp. 119-130
dc.identifier.issn	1084-8045
dc.identifier.issn	1095-8592
dc.identifier.uri	http://hdl.handle.net/10453/148525
dc.description.abstract	Influence maximization (IM) is the problem of finding a small subset of nodes in a social network so that the number of nodes influenced by this subset can be maximized. Influence maximization problem plays an important role in viral marketing and information diffusions. The existing solutions to influence maximization perform badly in either efficiency or accuracy. In this study, we analyze the causes for the low efficiency of the greedy approaches and propose a more efficient algorithm called degree-descending search evolution (DDSE). Firstly, we propose a degree-descending search strategy (DDS). DDS is capable of generating a node set whose influence spread is comparable to the degree centrality. Based on DDS, we develop an evolutionary algorithm that is capable of improving the efficiency significantly by eliminating the time-consuming simulations of the greedy algorithms. Experimental results on real-world social networks demonstrate that DDSE is about five orders of magnitude faster than the state-of-art greedy method while keeping competitive accuracy, which can verify the high effectiveness and efficiency of our proposed algorithm for influence maximization.
dc.language	English
dc.publisher	ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
dc.relation.ispartof	Journal of Network and Computer Applications
dc.relation.isbasedon	10.1016/j.jnca.2017.12.003
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0805 Distributed Computing, 1005 Communications Technologies
dc.subject.classification	Networking & Telecommunications
dc.title	DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks
dc.type	Journal Article
utslib.citation.volume	103
utslib.for	0805 Distributed Computing
utslib.for	1005 Communications Technologies
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2021-04-29T00:18:23Z
pubs.publication-status	Published
pubs.volume	103

Abstract:

Influence maximization (IM) is the problem of finding a small subset of nodes in a social network so that the number of nodes influenced by this subset can be maximized. Influence maximization problem plays an important role in viral marketing and information diffusions. The existing solutions to influence maximization perform badly in either efficiency or accuracy. In this study, we analyze the causes for the low efficiency of the greedy approaches and propose a more efficient algorithm called degree-descending search evolution (DDSE). Firstly, we propose a degree-descending search strategy (DDS). DDS is capable of generating a node set whose influence spread is comparable to the degree centrality. Based on DDS, we develop an evolutionary algorithm that is capable of improving the efficiency significantly by eliminating the time-consuming simulations of the greedy algorithms. Experimental results on real-world social networks demonstrate that DDSE is about five orders of magnitude faster than the state-of-art greedy method while keeping competitive accuracy, which can verify the high effectiveness and efficiency of our proposed algorithm for influence maximization.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/148525