Embedding diversity into knowledge discovery is important: the patterns mined will be more novel, more meaningful, and broader. Surprisingly, in the classic problem of influence maximization in social networks, relatively little study has been devoted to diversity and its integration into the objective function of an influence maximization method. In this work, we propose the integration of a categorical-based notion of seed diversity into the objective function of a targeted influence maximization problem. In this respect, we assume that the users of a social network are associated with a categorical dataset where each tuple expresses the profile of a user according to a predefined schema of categorical attributes. Upon this assumption, we design a class of monotone submodular functions specifically conceived for determining the diversity of the subset of categorical tuples associated with the seed users to be discovered. This allows us to develop an efficient approximate method, with a constant-factor guarantee of optimality. More precisely, we formulate the attribute-based diversity-sensitive targeted influence maximization problem under the state-of-the-art reverse influence sampling framework, and we develop a method, dubbed ADITUM, that ensures a (1-1/e-∊)-approximate solution under the general triggering diffusion model. Extensive experimental evaluation based on real-world networks as well as synthetically generated data has shown the meaningfulness and uniqueness of our proposed class of set diversity functions and of the ADITUM algorithm, also in comparison with methods that exploit numerical-attribute-based diversity and topology-driven diversity in influence maximization.

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.

What are the key-features that enable an information diffusion model to explain the inherent dynamic, and often competitive, nature of real-world propagation phenomena? In this paper we aim to answer this question by proposing a novel class of diffusion models, inspired by the classic Linear Threshold model, and built around the following aspects: trust/distrust in the user relationships, which is leveraged to model different effects of social influence on the decisions taken by an individual; changes in adopting one or alternative information items; hesitation towards adopting an information item over time; latency in the propagation; time horizon for the unfolding of the diffusion process; and multiple cascades of information that might occur competitively. To the best of our knowledge, the above aspects have never been unified into the same LT-based diffusion model. We also define different strategies for the selection of the initial influencers to simulate non-competitive and competitive diffusion scenarios, particularly related to the problem of limitation of misinformation spread. Results on publicly available networks have shown the meaningfulness and uniqueness of our models.