Paper Info
Title
Cores matter? An analysis of graph decomposition effects on influence maximization problems
Abstract
Estimating the spreading potential of nodes in a social network is an important problem which finds application in a variety of different contexts, ranging from viral marketing to spread of viruses and rumor blocking. Several studies have exploited both mesoscale structures and local centrality measures in order to estimate the spreading potential of nodes. To this end, one known result in the literature establishes a correlation between the spreading potential of a node and its coreness: i.e., in a core-decompostion of a network, nodes in higher cores have a stronger influence potential on the rest of the network. In this paper we show that the above result does not hold in general under common settings of propagation models with submodular activation function on directed networks, as those ones used in the influence maximization (IM) problem. Motivated by this finding, we extensively explore where the set of influential nodes extracted by state-of-the-art IM methods are located in a network w.r.t. different notions of graph decomposition. Our analysis on real-world networks provides evidence that, regardless of the particular IM method, the best spreaders are not always located within the inner-most subgraphs defined according to commonly used graph-decomposition methods. We identify the main reasons that explain this behavior, which can be ascribed to the inability of classic decomposition methods in incorporating higher-order degree of nodes. By contrast, we find that a distance-based generalization of the core-decomposition for directed networks can profitably be exploited to actually restrict the location of candidate solutions for IM to a single, well-defined portion of a network graph.
Year
DOI
Venue
2020
10.1145/3394231.3397908
WebSci '20: 12th ACM Conference on Web Science Southampton United Kingdom July, 2020
DocType
ISBN
Citations 
Conference
978-1-4503-7989-2
0
PageRank 
References 
Authors
0.34
23
3
Name
Order
Citations
PageRank
Antonio Caliò131.76
Andrea Tagarelli247552.29
Francesco Bonchi34173200.47