Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks
Article
Article Title | Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks |
---|---|
ERA Journal ID | 17876 |
Article Category | Article |
Authors | Cai, Taotao, Lei, Qi, Sheng, Quan Z., Cui, Ningning, Yang, Shuiqiao, Yang, Jian, Zhang, Wei Emma and Mahmood, Adnan |
Journal Title | IEEE Transactions on Knowledge and Data Engineering |
Journal Citation | 36 (5), pp. 2151-2165 |
Number of Pages | 15 |
Year | 2024 |
Publisher | IEEE (Institute of Electrical and Electronics Engineers) |
Place of Publication | United States |
ISSN | 1041-4347 |
1558-2191 | |
Digital Object Identifier (DOI) | https://doi.org/10.1109/TKDE.2023.3316268 |
Web Address (URL) | https://ieeexplore.ieee.org/abstract/document/10254336 |
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. |
Keywords | Evolving networks; graph query; influence maximization; link prediction |
Contains Sensitive Content | Does not contain sensitive content |
ANZSRC Field of Research 2020 | 460502. Data mining and knowledge discovery |
460299. Artificial intelligence not elsewhere classified | |
Public Notes | The accessible file is the accepted version of the paper. Please refer to the URL for the published version. |
Byline Affiliations | University of Southern Queensland |
Chang'an University, China | |
Macquarie University | |
Anhui University, China | |
Commonwealth Scientific and Industrial Research Organisation (CSIRO), Australia | |
University of Adelaide |
https://research.usq.edu.au/item/z4xx6/reconnecting-the-estranged-relationships-optimizing-the-influence-propagation-in-evolving-networks
Download files
52
total views30
total downloads4
views this month2
downloads this month