An Efficient Partition-Based Approach to Identify and Scatter Multiple Relevant Spreaders in Complex Networks
| Autor: | Victor J. Sosa-Sosa, Jedidiah Yanez-Sierra, Arturo Diaz-Perez |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Power graph analysis
Degree (graph theory) Computer science Science Physics QC1-999 Graph partition General Physics and Astronomy complex networks Complex network Astrophysics Network topology computer.software_genre Article QB460-466 communities spreaders selection Topological graph theory Graph (abstract data type) Data mining Centrality computer |
| Zdroj: | Entropy Volume 23 Issue 9 Entropy, Vol 23, Iss 1216, p 1216 (2021) |
| ISSN: | 1099-4300 |
| Popis: | One of the main problems in graph analysis is the correct identification of relevant nodes for spreading processes. Spreaders are crucial for accelerating/hindering information diffusion, increasing product exposure, controlling diseases, rumors, and more. Correct identification of spreaders in graph analysis is a relevant task to optimally use the network structure and ensure a more efficient flow of information. Additionally, network topology has proven to play a relevant role in the spreading processes. In this sense, more of the existing methods based on local, global, or hybrid centrality measures only select relevant nodes based on their ranking values, but they do not intentionally focus on their distribution on the graph. In this paper, we propose a simple yet effective method that takes advantage of the underlying graph topology to guarantee that the selected nodes are not only relevant but also well-scattered. Our proposal also suggests how to define the number of spreaders to select. The approach is composed of two phases: first, graph partitioning and second, identification and distribution of relevant nodes. We have tested our approach by applying the SIR spreading model over nine real complex networks. The experimental results showed more influential and scattered values for the set of relevant nodes identified by our approach than several reference algorithms, including degree, closeness, Betweenness, VoteRank, HybridRank, and IKS. The results further showed an improvement in the propagation influence value when combining our distribution strategy with classical metrics, such as degree, outperforming computationally more complex strategies. Moreover, our proposal shows a good computational complexity and can be applied to large-scale networks. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |