Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks

Cai, T; Lei, Q; Sheng, QZ; Cui, N; Yang, S; Yang, J; Zhang, WE; Mahmood, A

Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks

Cai, T Lei, Q Sheng, QZ Cui, N Yang, S

Yang, J Zhang, WE Mahmood, A

Permalink

Publisher:: IEEE COMPUTER SOC
Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2024, 36, (5), pp. 2151-2165
Issue Date:: 2024-05-01

Closed Access

	Filename	Description	Size
	1669743.pdf	Published version	2.26 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	Cai, T
dc.contributor.author	Lei, Q
dc.contributor.author	Sheng, QZ
dc.contributor.author	Cui, N
dc.contributor.author	Yang, S https://orcid.org/0000-0002-6772-6805
dc.contributor.author	Yang, J
dc.contributor.author	Zhang, WE
dc.contributor.author	Mahmood, A
dc.date.accessioned	2024-08-21T05:27:51Z
dc.date.available	2024-08-21T05:27:51Z
dc.date.issued	2024-05-01
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2024, 36, (5), pp. 2151-2165
dc.identifier.issn	1041-4347
dc.identifier.issn	1558-2191
dc.identifier.uri	http://hdl.handle.net/10453/180476
dc.description.abstract	Influence Maximization (IM), which aims to select a set of users from a social network to maximize the expected number of influenced users, has recently received significant attention for mass communication and commercial marketing. Existing research efforts dedicated to the IM problem depend on a strong assumption: the selected seed users are willing to spread the information after receiving benefits from a company or organization. In reality, however, some seed users may be reluctant to spread the information or need to be paid higher to be motivated. Furthermore, the existing IM works pay little attention to capture users' influence propagation in the future period. In this paper, we target a new research problem named, Reconnecting Top-l Relationships (RT l R) query, which aims to find l number of previous existing relationships but being estranged later such that reconnecting these relationships will maximize the expected number of influenced users by the given group in a future period. We prove that the RT l R problem is NP-hard. An efficient greedy algorithm is proposed to answer the RT l R queries with the influence estimation technique and the well-chosen link prediction method to predict the near future network structure. We also design a pruning method to reduce unnecessary probing from candidate edges. Further, a carefully designed order-based algorithm is proposed to accelerate the RT l R queries. Finally, we conduct extensive experiments on real-world datasets to demonstrate the effectiveness and efficiency of our proposed methods.
dc.language	English
dc.publisher	IEEE COMPUTER SOC
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering
dc.relation.isbasedon	10.1109/TKDE.2023.3316268
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	08 Information and Computing Sciences
dc.subject.classification	Information Systems
dc.subject.classification	46 Information and computing sciences
dc.title	Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks
dc.type	Journal Article
utslib.citation.volume	36
utslib.for	08 Information and Computing Sciences
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/A/DRsch The Data Science Institute
utslib.copyright.status	closed_access	*
dc.date.updated	2024-08-21T05:27:49Z
pubs.issue	5
pubs.publication-status	Published
pubs.volume	36
utslib.citation.issue	5

Abstract:

Influence Maximization (IM), which aims to select a set of users from a social network to maximize the expected number of influenced users, has recently received significant attention for mass communication and commercial marketing. Existing research efforts dedicated to the IM problem depend on a strong assumption: the selected seed users are willing to spread the information after receiving benefits from a company or organization. In reality, however, some seed users may be reluctant to spread the information or need to be paid higher to be motivated. Furthermore, the existing IM works pay little attention to capture users' influence propagation in the future period. In this paper, we target a new research problem named, Reconnecting Top-l Relationships (RT l R) query, which aims to find l number of previous existing relationships but being estranged later such that reconnecting these relationships will maximize the expected number of influenced users by the given group in a future period. We prove that the RT l R problem is NP-hard. An efficient greedy algorithm is proposed to answer the RT l R queries with the influence estimation technique and the well-chosen link prediction method to predict the near future network structure. We also design a pruning method to reduce unnecessary probing from candidate edges. Further, a carefully designed order-based algorithm is proposed to accelerate the RT l R queries. Finally, we conduct extensive experiments on real-world datasets to demonstrate the effectiveness and efficiency of our proposed methods.

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

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