Page 53 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2016 3rd Student Computer Science Research Conference. Koper: University of Primorska Press, 2016

INFLUENCE-MAXIMIZATION
At the original model a function σ(·) is given at the IC model To accelarate our methods we have to reduce the solution
and we are looking for the set, for which the function is
maximal. For the general case a function w of probabilities
is given a priori and it is not obvious how we can maximize
it. We defined two problems to analyze the function. They
are positive and negative influence maximization problem
connection with spreading of positive and negative effect.
3.1 Influence-maximization in the GIC
Because the influence-maximization problem has not been
defined for more general cases, we defined two infection-
maximization problems. Both problems have modified in-
put probabilities. For the positive case we defined probabil-
ity values, which are greater than zero on vertices of initial
vertex set. It is zero on the other vertices. An example
for the positive case is product affinity, which is measured
by the reaction of the clients for a product at the service
sector. An example for the negative infection maximization
model is churn prediction. We measure the relationship be-
tween the clients and the service provider. We would like to
maximize the minimal churn. In this case there are the so
called ‘uplift’ probability values, which are given at initial wup less than input infection w at network G and case of
vertices of vertex set. These values are measured for the
clients at the service providers. The vertices that are not in mal value on the set A ⊆ V ∗.
the initial vertex set can be measured by the original prob-
ability values. These values give the size of the client churn 4. SOLUTION METHODS
at companies. The formally definitions of tasks are the next:
Definition 1. (Positive influence maximization model) Hav-
ing a network G, where a set A ⊂ V . Let w function of
weights, and F a GIC model. Furthermore let wpA,v the mod-
ified input probability, where
• ∀v ∈ A, wpA,v = wv
• ∀v ∈/ A, wpA,v = 0.
Optimization task: Search set A with k elements, where
σp(A) = σ(wpA) is maximal.
Thus elements of A get values according to w, another ele-
ments (V \ A) get zero.
Definition 2. (Negative influence maximization model) An
IC model which of input infection have a wnA,v modified input
probability, where
• ∀v ∈ A, wnA,v = wvup, uplift probability
• ∀v ∈/ A, wnA,v = wv.
Optimization task: Search set A with k elements, where
σn(A) = σ(w) − σ(wnA) is maximal.
Thus elements of A get values according to an uplift func-
tion, another elements (V \ A) get values according to w.
At the campain of the products k clients are targeted for
both cases. At the current infection process step all suscep-
tible elements will be activated according to their edge and
vertex probabilities.
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 53
Ljubljana, Slovenia, 12 October
3.2 Reducing the solution space
space. The elements of the initial set of vertices are from the
set of which the elements have positive input probability at
the positive case. At the negative case there are only those
elements in the initial set which are smaller than the input
value. This reduction is useful because the excluded ele-
ments are not important at calculating the estimated proba-
bility of the network. In this case the influence-maximization
problem is to find reduced set V an initial set A with given
k elements, where these elements have maximal infection.
Formally let v ∈ V :
• Positive case: if wv > 0, then v ∪ V ∗
• Negative case: if wvup < wv, then v ∪ V ∗
We prove that we can get optimal value after the reduction.
Lemma 1. Let V ∗ denote elements of V , for which the
input infection w is positive at network G and case of GIC
model. Thus, infection function σpG(w) gets its optimal value
on the set A ⊆ V ∗.
Lemma 2. Let V ∗ denote elements of V , for which value
GIC model. Thus, infection function σnG(wn) gets its opti-
Since Kempe et al. in [7] realized that approximation of the
optimum of the complex task can be given with arbitrary
precision with the help of a greedy algorithm, it seems nat-
ural to use it at the general case. We illustrate what type
of acceleration can be used for the calculation.
4.1 Greedy framework
In this section we introduce a theorem which can be used for
the specified two tasks and we show the proof. To present
our results, we need to introduce some concepts based on
[7]. We said that function f is submodular if it satisfies a
natural ‘diminishing returns’ property: the marginal gain
from adding the same element to a superset of S. Formally,
a submodular function satisfies
f (S ∪ {v}) − f (S) ≥ f (T ∪ {v}) − f (T ),
for all elements v and all pairs of sets S ⊆ T . And a function
f monotone if adding an element to a set cannot cause f to
decrease:
f (S ∪ {v}) ≥ f (S).
The greedy method starts from an empty set. It repeatedly
adds the vertex x to set A maximizing the marginal gain
g(A ∪ {x}) − g(A) if having a submodular function g. [3]
In [8] Nemhauser et al. studied the monotone, submodular
functions:
Theorem 1. Let σ(·) denote a non-negative, monotone,
submodular function. Then the greedy algorithm (for k iter-
ations) adds an element with the largest marginal increase
in σ(·) produces a k-element set A such that
σ(A) ≥ (1 − 1/e) · max|B|=kσ(B)