Page 73 - 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. 73
Table 1: Comparison of the models
Covering problem Influence maximization
graph of demand points and roads social network (graph)
we want to locate facilities at demand points (vertices) we want to find the seed points (vertices)
cover other demand points influence other points
Covering: a demand point is covered if there is a company Influencing: a point is influenced, if any neighbour could
for which their distance is less than the coverage distance influence it with the probability of the edge
static, only facilities can cover dynamic, anyone can influence
edge weights are distances edge weights are probabilities
deterministic stochastic
4. COMPARISON OF THE MODELS The modified triggering model can be solved by the opti-
mization problem in (1-3) where the maximum number of
Let’s first look at the similarities and differences between steps is set to R, and Tj is the triggering set for each vertex,
the two models in general, summarized in Table 1. being the set of all the neighbours of j.
Both models work with simple graphs and choose vertices Let us show that the model (1-3) is equivalent to the max-
based on the weights of the edges. None of the models need imal covering model (4-6). As a first step, let us rewrite
to add any new point, just choose one or more from the ex- the condition (6) without the parameter aij, only relying on
isting vertices (these are going to be the seeds or centers), d(i, j), the distance of vertices i and j.
and either spread the information to the neighbours or be
the location for the new facilities. The aim of both models is Xi ≥ Yj ∀j (7)
to reach as many points as possible. However, the definition
and the way the seeds reach the other vertices are different. i∈V :d(i,j)≤R
We count a point as covered if there is at least one facility
where their distance, that is the total weight of the shortest Now, in order to show the equivalence, we write the models
path between the demand point and the new company, is less side by side, where in each line the corresponding parts are
than the given covering distance. We count a point as influ- given.
enced if at least one of its neighbours influence it with the
edge probability between them. Thus, one of the largest dif- max Yj max ZjR (8)
ference is that the maximal covering problem is static, while s.t.
the information diffusion is dynamic.You: Besides these, an- j j
other difference is, that in the covering model only the new ∀i
facility or facilities can cover the demand points, while in s.t. Xj = s Zj0 = s (9)
the influence maximization problem every influenced point
can further influence its neighbours. In the first case, there j j
is a concrete distance, whilst in the second case, there are
only probabilities for the spreading, where the spreading can Xj ≥ Yi Zit ≥ Zj,t+1 (10)
take any number of steps. It also means that covering is
deterministic, as the coverage is always the same, while in- j∈V :d(i,j)≤R i∈Tj
formation diffusion is stochastic, as every time we generate
random values to simulate the spreading. ∀j, 0 ≤ t < R
4.1 Comparison of a modified triggering For the variables, Yj ≡ ZjR, and Xj ≡ Zj0, which makes
model and the maximal covering model the equivalence in lines (8-9) obvious. In order to see that
the conditions in (10) are defining the same constraints, let
A modified triggering model may provide a solution to over- is rewrite the influence condition as follows.
come these differences. To repeat, in the triggering model,
each point independently selects a random set (triggering Aggregating k∈Ti Zk,t−1 ≥ Zit and i∈Tj Zit ≥ Zj,t+1 we
set Tj) based on the distribution of subsets of the neigh- obtain
bours. If one point in Tj becomes active, so does the point
j. This will result in two types of edges, ”live” and ”blocked” Zk,t−1 ≥ Zj,t+1
as they belong to the triggering set or not. Now, considering
the sub-graph with only the ”live” edges, and restricting the k∈Ti i∈Tj
run time of the triggering model to R number of steps, the
problem equivalent to the maximal covering problem on the and following this for all the R steps, the condition becomes
sub-graph with covering radius R.
· · · Zi0,0 ≥ Zj,R
Therefore, we propose to modify the triggering model by
setting a maximum time for the spread of information, that i0∈Ti1 i1∈Ti2 iR−1 ∈Tj
is the number of steps.
Now, if we take into account, that the above sums are only
adding those Zi0,0, where i0 ∈ Ti1 , i1 ∈ Ti2 , . . . , iR−1 ∈ Tj ,
the requirement is actually the same as d(i0, j) ≤ R. There-
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 73
Koper, Slovenia, 10 October
Covering problem Influence maximization
graph of demand points and roads social network (graph)
we want to locate facilities at demand points (vertices) we want to find the seed points (vertices)
cover other demand points influence other points
Covering: a demand point is covered if there is a company Influencing: a point is influenced, if any neighbour could
for which their distance is less than the coverage distance influence it with the probability of the edge
static, only facilities can cover dynamic, anyone can influence
edge weights are distances edge weights are probabilities
deterministic stochastic
4. COMPARISON OF THE MODELS The modified triggering model can be solved by the opti-
mization problem in (1-3) where the maximum number of
Let’s first look at the similarities and differences between steps is set to R, and Tj is the triggering set for each vertex,
the two models in general, summarized in Table 1. being the set of all the neighbours of j.
Both models work with simple graphs and choose vertices Let us show that the model (1-3) is equivalent to the max-
based on the weights of the edges. None of the models need imal covering model (4-6). As a first step, let us rewrite
to add any new point, just choose one or more from the ex- the condition (6) without the parameter aij, only relying on
isting vertices (these are going to be the seeds or centers), d(i, j), the distance of vertices i and j.
and either spread the information to the neighbours or be
the location for the new facilities. The aim of both models is Xi ≥ Yj ∀j (7)
to reach as many points as possible. However, the definition
and the way the seeds reach the other vertices are different. i∈V :d(i,j)≤R
We count a point as covered if there is at least one facility
where their distance, that is the total weight of the shortest Now, in order to show the equivalence, we write the models
path between the demand point and the new company, is less side by side, where in each line the corresponding parts are
than the given covering distance. We count a point as influ- given.
enced if at least one of its neighbours influence it with the
edge probability between them. Thus, one of the largest dif- max Yj max ZjR (8)
ference is that the maximal covering problem is static, while s.t.
the information diffusion is dynamic.You: Besides these, an- j j
other difference is, that in the covering model only the new ∀i
facility or facilities can cover the demand points, while in s.t. Xj = s Zj0 = s (9)
the influence maximization problem every influenced point
can further influence its neighbours. In the first case, there j j
is a concrete distance, whilst in the second case, there are
only probabilities for the spreading, where the spreading can Xj ≥ Yi Zit ≥ Zj,t+1 (10)
take any number of steps. It also means that covering is
deterministic, as the coverage is always the same, while in- j∈V :d(i,j)≤R i∈Tj
formation diffusion is stochastic, as every time we generate
random values to simulate the spreading. ∀j, 0 ≤ t < R
4.1 Comparison of a modified triggering For the variables, Yj ≡ ZjR, and Xj ≡ Zj0, which makes
model and the maximal covering model the equivalence in lines (8-9) obvious. In order to see that
the conditions in (10) are defining the same constraints, let
A modified triggering model may provide a solution to over- is rewrite the influence condition as follows.
come these differences. To repeat, in the triggering model,
each point independently selects a random set (triggering Aggregating k∈Ti Zk,t−1 ≥ Zit and i∈Tj Zit ≥ Zj,t+1 we
set Tj) based on the distribution of subsets of the neigh- obtain
bours. If one point in Tj becomes active, so does the point
j. This will result in two types of edges, ”live” and ”blocked” Zk,t−1 ≥ Zj,t+1
as they belong to the triggering set or not. Now, considering
the sub-graph with only the ”live” edges, and restricting the k∈Ti i∈Tj
run time of the triggering model to R number of steps, the
problem equivalent to the maximal covering problem on the and following this for all the R steps, the condition becomes
sub-graph with covering radius R.
· · · Zi0,0 ≥ Zj,R
Therefore, we propose to modify the triggering model by
setting a maximum time for the spread of information, that i0∈Ti1 i1∈Ti2 iR−1 ∈Tj
is the number of steps.
Now, if we take into account, that the above sums are only
adding those Zi0,0, where i0 ∈ Ti1 , i1 ∈ Ti2 , . . . , iR−1 ∈ Tj ,
the requirement is actually the same as d(i0, j) ≤ R. There-
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 73
Koper, Slovenia, 10 October
