Page 71 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 71
ering problems and Influence maximization
Gyöngyvér Vass Boglárka G.-Tóth
Institute of Informatics Institute of Informatics
University of Szeged University of Szeged
Szeged, Hungary Szeged, Hungary
Vass.Gyongyver@stud.u-szeged.hu boglarka@inf.szte.hu
ABSTRACT Covering models, Influence maximization, Mixed Integer
Programming
Influence maximization is a very popular problem in the
social sciences. It seeks a given number of seed points (ver- 1. INTRODUCTION
tices) in a network to maximize the number of influenced ver-
tices starting from the seeds. Influencing may occur trough The influence maximization problem explores that from a
the edges, which indicate the connection between people given seed point how many other individuals can be reached
(vertices). There are different ways to define influence, but by the information in a social network. The transmitting
up to our knowledge, finding the seeds from which maximal of the information and the terms of the transmitting can
influence can be reached is a difficult task in general. be different, but usually, the capability of the influencing is
impressed by the weight or strength of the edge between two
Coverage models belong to facility location problems, where points. Influence maximization is also known as information
centers are to be located such that the covered demand diffusion. For a survey on the subject see [2, 3].
points (vertices in a graph within a given distance) are maxi-
mized. These models are motivated by problems where some In facility location, the covering problem explores the point
services are only available within a fixed radius, like ambu- or points that can cover other points in a demand network
lances or fast food delivery. These problems are solvable for within a given covering distance. For a good introduction
large graphs, and our long term aim is to use the most appro- to facility location problems, see [1].
priate and/or adjusted covering models for solving influence
maximization problems. As a first step, in this paper, we Up to the knowledge of the authors, these models have not
compare influence maximization and coverage models and yet been compared in the literature, thus results in this pa-
analyze their differences. per are completely novel. As covering models are well stud-
ied and efficient algorithms exist to solve large scale prob-
As we will show, there are many similarities between the lems, it is interesting to investigate if the influence maxi-
models, however, the main difference is that covering is a mization problem (or its slight modification) can be solved
static action while influencing is dynamic. We show when by any approach made for covering models. Thus, we aim
this difference can be resolved, and how different are the to compare influence maximization and covering models as
results when not. a first step.
Categories and Subject Descriptors 2. INFLUENCE MAXIMIZATION
G.2.2 [Mathematics of Computing]: Graph TheoryNet- Formally, the influence maximization problem can be de-
work problems; G.1.6 [Mathematics of Computing]: Op- fined as follows. There is a simple graph G = (V, E), where
timization the vertices of the graph v ∈ V represent the individuals and
the edges represent the connections between them. Here-
General Terms after we can regard as |V | = n and |E| = m, thus, in the
social network there are n people, and m connections be-
Theory, application tween them. We assign a weight to each edge e ∈ E, which
will give us a probability: f (e) : E → [0, 1] the probability
Keywords that information can spread trough a given edge e, also it
can be seen as the strength of the relationship.
For the influence maximization model, there is a set S ⊂ V ,
from which the information will start, called seed set. The
cardinality of the set S is fixed, we will denote it with s
(s < n). This gives us a general diffusion model, where the
diffusion function is: σ(S) : V → [s, n], that is, the number
of vertices influenced by the seed set S. We seek for the seed
set maximizing the influence, i.e. maxS⊂V σ(S).
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.71-74 71
Koper, Slovenia, 10 October
Gyöngyvér Vass Boglárka G.-Tóth
Institute of Informatics Institute of Informatics
University of Szeged University of Szeged
Szeged, Hungary Szeged, Hungary
Vass.Gyongyver@stud.u-szeged.hu boglarka@inf.szte.hu
ABSTRACT Covering models, Influence maximization, Mixed Integer
Programming
Influence maximization is a very popular problem in the
social sciences. It seeks a given number of seed points (ver- 1. INTRODUCTION
tices) in a network to maximize the number of influenced ver-
tices starting from the seeds. Influencing may occur trough The influence maximization problem explores that from a
the edges, which indicate the connection between people given seed point how many other individuals can be reached
(vertices). There are different ways to define influence, but by the information in a social network. The transmitting
up to our knowledge, finding the seeds from which maximal of the information and the terms of the transmitting can
influence can be reached is a difficult task in general. be different, but usually, the capability of the influencing is
impressed by the weight or strength of the edge between two
Coverage models belong to facility location problems, where points. Influence maximization is also known as information
centers are to be located such that the covered demand diffusion. For a survey on the subject see [2, 3].
points (vertices in a graph within a given distance) are maxi-
mized. These models are motivated by problems where some In facility location, the covering problem explores the point
services are only available within a fixed radius, like ambu- or points that can cover other points in a demand network
lances or fast food delivery. These problems are solvable for within a given covering distance. For a good introduction
large graphs, and our long term aim is to use the most appro- to facility location problems, see [1].
priate and/or adjusted covering models for solving influence
maximization problems. As a first step, in this paper, we Up to the knowledge of the authors, these models have not
compare influence maximization and coverage models and yet been compared in the literature, thus results in this pa-
analyze their differences. per are completely novel. As covering models are well stud-
ied and efficient algorithms exist to solve large scale prob-
As we will show, there are many similarities between the lems, it is interesting to investigate if the influence maxi-
models, however, the main difference is that covering is a mization problem (or its slight modification) can be solved
static action while influencing is dynamic. We show when by any approach made for covering models. Thus, we aim
this difference can be resolved, and how different are the to compare influence maximization and covering models as
results when not. a first step.
Categories and Subject Descriptors 2. INFLUENCE MAXIMIZATION
G.2.2 [Mathematics of Computing]: Graph TheoryNet- Formally, the influence maximization problem can be de-
work problems; G.1.6 [Mathematics of Computing]: Op- fined as follows. There is a simple graph G = (V, E), where
timization the vertices of the graph v ∈ V represent the individuals and
the edges represent the connections between them. Here-
General Terms after we can regard as |V | = n and |E| = m, thus, in the
social network there are n people, and m connections be-
Theory, application tween them. We assign a weight to each edge e ∈ E, which
will give us a probability: f (e) : E → [0, 1] the probability
Keywords that information can spread trough a given edge e, also it
can be seen as the strength of the relationship.
For the influence maximization model, there is a set S ⊂ V ,
from which the information will start, called seed set. The
cardinality of the set S is fixed, we will denote it with s
(s < n). This gives us a general diffusion model, where the
diffusion function is: σ(S) : V → [s, n], that is, the number
of vertices influenced by the seed set S. We seek for the seed
set maximizing the influence, i.e. maxS⊂V σ(S).
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.71-74 71
Koper, Slovenia, 10 October
