We live in a world of social networks. Our everyday choices are often influenced by social interactions. Word of mouth, meme di↵usion on the Internet, and viral marketing are all examples of how social networks can a↵ect our behaviour. In many practical applications, it is of great interest to determine which nodes have the highest influence over the network, i.e., which set of nodes will, indirectly, reach the largest audience when propagating information. These nodes might be, for instance, the target for early adopters of a product, the most influential endorsers in political elections, or the most important investors in financial operations, just to name a few examples. Here, we tackle the NP-hard problem of influence maximization on social networks by means of a Genetic Algorithm. We show that, by using simple genetic operators, it is possible to find in feasible runtime solutions of high-influence that are comparable, and occasionally better, than the solutions found by a number of known heuristics (one of which was previously proven to have the best possible approximation guarantee, in polynomial time, of the optimal solution). The advantages of Genetic Algorithms show, however, in them not requiring any assumptions about the graph underlying the network, and in them obtaining more diverse sets of feasible solutions than current heuristics.

Influence Maximization in Social Networks with Genetic Algorithms / Bucur, Doina; Iacca, Giovanni. - 9597:(2016), pp. 379-392. (Intervento presentato al convegno EvoApplications 2016 tenutosi a Porto, Portugal nel 30th March-1st April 2016) [10.1007/978-3-319-31204-0_25].

Influence Maximization in Social Networks with Genetic Algorithms

Iacca, Giovanni
2016-01-01

Abstract

We live in a world of social networks. Our everyday choices are often influenced by social interactions. Word of mouth, meme di↵usion on the Internet, and viral marketing are all examples of how social networks can a↵ect our behaviour. In many practical applications, it is of great interest to determine which nodes have the highest influence over the network, i.e., which set of nodes will, indirectly, reach the largest audience when propagating information. These nodes might be, for instance, the target for early adopters of a product, the most influential endorsers in political elections, or the most important investors in financial operations, just to name a few examples. Here, we tackle the NP-hard problem of influence maximization on social networks by means of a Genetic Algorithm. We show that, by using simple genetic operators, it is possible to find in feasible runtime solutions of high-influence that are comparable, and occasionally better, than the solutions found by a number of known heuristics (one of which was previously proven to have the best possible approximation guarantee, in polynomial time, of the optimal solution). The advantages of Genetic Algorithms show, however, in them not requiring any assumptions about the graph underlying the network, and in them obtaining more diverse sets of feasible solutions than current heuristics.
2016
Applications of Evolutionary Computation
Cham
Springer
978-3-319-31203-3
978-3-319-31204-0
Bucur, Doina; Iacca, Giovanni
Influence Maximization in Social Networks with Genetic Algorithms / Bucur, Doina; Iacca, Giovanni. - 9597:(2016), pp. 379-392. (Intervento presentato al convegno EvoApplications 2016 tenutosi a Porto, Portugal nel 30th March-1st April 2016) [10.1007/978-3-319-31204-0_25].
File in questo prodotto:
File Dimensione Formato  
bucur.pdf

accesso aperto

Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 676.94 kB
Formato Adobe PDF
676.94 kB Adobe PDF Visualizza/Apri

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/11572/196444
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 67
  • ???jsp.display-item.citation.isi??? 63
social impact