Malliaros Fragkiskos D, Rossi Maria-Evgenia G, Vazirgiannis Michalis
Computer Science Laboratory, École Polytechnique, 91120 Palaiseau, France.
Sci Rep. 2016 Jan 18;6:19307. doi: 10.1038/srep19307.
Understanding and controlling spreading processes in networks is an important topic with many diverse applications, including information dissemination, disease propagation and viral marketing. It is of crucial importance to identify which entities act as influential spreaders that can propagate information to a large portion of the network, in order to ensure efficient information diffusion, optimize available resources or even control the spreading. In this work, we capitalize on the properties of the K-truss decomposition, a triangle-based extension of the core decomposition of graphs, to locate individual influential nodes. Our analysis on real networks indicates that the nodes belonging to the maximal K-truss subgraph show better spreading behavior compared to previously used importance criteria, including node degree and k-core index, leading to faster and wider epidemic spreading. We further show that nodes belonging to such dense subgraphs, dominate the small set of nodes that achieve the optimal spreading in the network.
理解和控制网络中的传播过程是一个重要的主题，具有许多不同的应用，包括信息传播、疾病传播和病毒式营销。识别哪些实体充当有影响力的传播者，能够将信息传播到网络的很大一部分，这对于确保有效的信息扩散、优化可用资源甚至控制传播至关重要。在这项工作中，我们利用K-桁架分解的特性（一种基于三角形的图核心分解扩展）来定位单个有影响力的节点。我们对真实网络的分析表明，与先前使用的重要性标准（包括节点度和k-核指数）相比，属于最大K-桁架子图的节点表现出更好的传播行为，从而导致更快、更广泛的流行病传播。我们进一步表明，属于此类密集子图的节点主导了在网络中实现最佳传播的一小部分节点。
