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.

Attribute based diversification of seeds for targeted influence maximization

Tagarelli A.
2021-01-01

Abstract

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.
2021
Diversity in influence maximization
Monotone submodular categorical set functions
Reverse influence sampling
Social recommendation
Viral marketing
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/313118
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? ND
social impact