Jelenlegi hely


2021/22 I. félév
Árpád tér 2. Alagsor 6.
Gyöngyvér Vass
Influence Maximization by Facility Location

Influence maximization is a very popular problem in social sciences. It seeks a given number of seed points (vertices) in a network to maximize the number of influenced vertices starting from the seeds. Influencing may occur through the edges, which indicate the connection between people (vertices). There are different ways to define influence, but finding the seeds from which maximal influence can be reached is a difficult task in general.

Covering models belong to facility location problems, where facilities are to be located such that the covered demand points (vertices in a graph within a given distance) are maximized. These problems are solvable for large graphs, and our long-term aim is to use the most appropriate and/or adjusted covering models for solving influence maximization problems.

We have compared influence maximization and covering models and analysed their differences.  We have found that the Triggering influence maximization model can be made equivalent to a maximal covering model.  For the Independent Cascade model, we defined the edge lengths  from  the  probabilities  of  the  influence,  and showed  experimentally that the solution of the maximal covering model gives very good approximation for the maximal influencers.