Discovering fortress-like cohesive subgraphs

作者:Conggai Li, Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, Xuemin Lin

摘要

Morris (Rev Econ Stud 67:57–78, 2000) defines the \(p\)-cohesion by a connected subgraph in which every vertex has at least a fraction p of its neighbors in the subgraph, i.e., at most a fraction (\(1-p\)) of its neighbors outside. We can find that a \(p\)-cohesion ensures not only inner-cohesiveness but also outer-sparseness. The textbook on networks by Easley and Kleinberg  (Networks, Crowds, and Markets - Reasoning About a Highly Connected World, Cambridge University Press, 2010) shows that \(p\)-cohesions are fortress-like cohesive subgraphs which can hamper the entry of the cascade, following the contagion model. Despite the elegant definition and promising properties, to our best knowledge, there is no existing study on \(p\)-cohesion regarding problem complexity and efficient computing algorithms. In this paper, we fill this gap by conducting a comprehensive theoretical analysis on the complexity of the problem and developing efficient computing algorithms. We focus on the minimal \(p\)-cohesion because they are elementary units of \(p\)-cohesions and the combination of multiple minimal \(p\)-cohesions is a larger \(p\)-cohesion. We demonstrate that the discovered minimal \(p\)-cohesions can be utilized to solve the MinSeed problem: finding a smallest set of initial adopters (seeds) such that all the network users are eventually influenced. Extensive experiments on 8 real-life social networks verify the effectiveness of this model and the efficiency of our algorithms.

论文关键词:Cohesive subgraph, Information barrier, Social network, MinSeed

论文评审过程:

论文官网地址:https://doi.org/10.1007/s10115-021-01624-x