Page 51 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2016 3rd Student Computer Science Research Conference. Koper: University of Primorska Press, 2016
P. 51
edy Heuristics for the Generalized Independent
Cascade Model
László Tóth
University of Szeged
13 Dugonics Squere
Szeged, Hungary
tlaszlo@inf.u-szeged.hu
ABSTRACT in practice. In [2] Bo´ta et al. extended the model and in-
troduced the Generalized Independent Cascade Model. The
In this paper we formulate optimization problems for the initial state of this model does not consist of infected and
Generalzed Independent Cascade Model, which is introduced uninfected vertices, but introduces an a priori probability
by Bota et al. The purpose of these tasks is to define the size of infection for each vertex. Each vertex receives an a pos-
k which cause the greatest infection in a network. We show teriori infection value by the end of the infection process.
that a greedy heuristic ensure the theoretically guaranteed Because the infection process above is #P-complete, [2] in-
precision for the problems. Finally we investigate the our troduces a number of approximation algorithms. In turn,
methods with practical tests. the influence-maximization problem has not been defined
for this more general case.
Keywords
In this paper we define two infection-maximization prob-
Influence Maximization, Generalized Independent Cascade lems connected to the generalized model above. They are
Model, Greedy Heuristics the positive and the negative problems. At the positive task
every elements of a social network have a probability val-
Supervisor ues, so-called ’input’ values. These values are considered
if a element is part of the inintial infection set, the other
Dr. Miklo´s Kr´esz values is zero during the positive infection process. At the
Department of Applied Informatics, end of this the amount of the probability values of infected
University of Szeged, Hungary vertices mean the a posteriori value of the current process.
Contact: kresz@jgypk.szte.hu If we model a campain of a product we can take an affinity
analysis. The optimization problem for this task is to find
1. INTRODUCTION the expected value of the maximal number of the infected
elements. At the introduced negative task we assume that
We usually think about medical science if we hear about a firm would like to increase the clients of ’churn incliation’
the infection. It also appeared in the sociology in the early with help of a offered products. In this case every single ele-
years of scientific modeling, then some sociologist start to ments (clients) have another values, so-called ’uplift’ values
use Linear Threshold Model (in [5]) and try to model differ- as the measure of the churn willingness. The method calcu-
ent social effect. Therefore, economist discovered that the lates with uplift values of the elements if the they are part of
modified version of threshold model (Independent Cascade the initial set, otherwise with the The related optimization
Model, in [4]) is suitable to help research of business process. problem is to find the minimal churn incliation.
This model is the most important break-through the theory
of computation point of view. The infection spreads in so- We also present solution methods based on greedy heuris-
cial networks the following way: we choose an initial infected tics, and compare their results with each other. We prove
vertex set, and only those vertices spread the infection after that a guaranteed approximation precision can be achieved
this that became infected in the previous iteration. Every for these greedy algorithms. To guarantee efficiency from a
edge start from an infected vertex has a single chance for in- practical point of view, we decrease the search space for the
fecting using its own infection probability. Kempe et al. [6] greedy methods using different approaches (e.g. selection
defined the influence-maximization problem, where we look based on vertex degree). In our test cases we compared this
the highest. This problem is NP-complete, but Kempe et heuristics with help of generated graphs.
al. proved in [6] that applying a greedy algorithm gives a
guaranteed precision that results in good quality solutions
2. INFECTION MODELS
The aim of this chapter is to introduce the main definition
of our topic. The basic definitions and concepts related to
graph theory are based on [10]. A simple graph is a G =
(V, E) structure, where V is a finite vertex or vertex set, E
is the edge set. There are probabilities on the edges and the
infection is spread helping these values according to a given
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 51
Ljubljana, Slovenia, 12 October
Cascade Model
László Tóth
University of Szeged
13 Dugonics Squere
Szeged, Hungary
tlaszlo@inf.u-szeged.hu
ABSTRACT in practice. In [2] Bo´ta et al. extended the model and in-
troduced the Generalized Independent Cascade Model. The
In this paper we formulate optimization problems for the initial state of this model does not consist of infected and
Generalzed Independent Cascade Model, which is introduced uninfected vertices, but introduces an a priori probability
by Bota et al. The purpose of these tasks is to define the size of infection for each vertex. Each vertex receives an a pos-
k which cause the greatest infection in a network. We show teriori infection value by the end of the infection process.
that a greedy heuristic ensure the theoretically guaranteed Because the infection process above is #P-complete, [2] in-
precision for the problems. Finally we investigate the our troduces a number of approximation algorithms. In turn,
methods with practical tests. the influence-maximization problem has not been defined
for this more general case.
Keywords
In this paper we define two infection-maximization prob-
Influence Maximization, Generalized Independent Cascade lems connected to the generalized model above. They are
Model, Greedy Heuristics the positive and the negative problems. At the positive task
every elements of a social network have a probability val-
Supervisor ues, so-called ’input’ values. These values are considered
if a element is part of the inintial infection set, the other
Dr. Miklo´s Kr´esz values is zero during the positive infection process. At the
Department of Applied Informatics, end of this the amount of the probability values of infected
University of Szeged, Hungary vertices mean the a posteriori value of the current process.
Contact: kresz@jgypk.szte.hu If we model a campain of a product we can take an affinity
analysis. The optimization problem for this task is to find
1. INTRODUCTION the expected value of the maximal number of the infected
elements. At the introduced negative task we assume that
We usually think about medical science if we hear about a firm would like to increase the clients of ’churn incliation’
the infection. It also appeared in the sociology in the early with help of a offered products. In this case every single ele-
years of scientific modeling, then some sociologist start to ments (clients) have another values, so-called ’uplift’ values
use Linear Threshold Model (in [5]) and try to model differ- as the measure of the churn willingness. The method calcu-
ent social effect. Therefore, economist discovered that the lates with uplift values of the elements if the they are part of
modified version of threshold model (Independent Cascade the initial set, otherwise with the The related optimization
Model, in [4]) is suitable to help research of business process. problem is to find the minimal churn incliation.
This model is the most important break-through the theory
of computation point of view. The infection spreads in so- We also present solution methods based on greedy heuris-
cial networks the following way: we choose an initial infected tics, and compare their results with each other. We prove
vertex set, and only those vertices spread the infection after that a guaranteed approximation precision can be achieved
this that became infected in the previous iteration. Every for these greedy algorithms. To guarantee efficiency from a
edge start from an infected vertex has a single chance for in- practical point of view, we decrease the search space for the
fecting using its own infection probability. Kempe et al. [6] greedy methods using different approaches (e.g. selection
defined the influence-maximization problem, where we look based on vertex degree). In our test cases we compared this
the highest. This problem is NP-complete, but Kempe et heuristics with help of generated graphs.
al. proved in [6] that applying a greedy algorithm gives a
guaranteed precision that results in good quality solutions
2. INFECTION MODELS
The aim of this chapter is to introduce the main definition
of our topic. The basic definitions and concepts related to
graph theory are based on [10]. A simple graph is a G =
(V, E) structure, where V is a finite vertex or vertex set, E
is the edge set. There are probabilities on the edges and the
infection is spread helping these values according to a given
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 51
Ljubljana, Slovenia, 12 October
