In this work, we consider the problem of influence maximization on a hypergraph. We first extend the Independent Cascade (IC) model to hypergraphs, and prove that the traditional influence maximization problem remains submodular. We then present a variant of the influence maximization problem (HEMI) where one seeks to maximize the number of hyperedges, a majority of whose nodes are influenced. We prove that HEMI is non-submodular under the difusion model proposed.
Influence maximization [
The problem first requires a specification of difusion model, which specifies how the set of influenced nodes at time t afects the set of non-influenced node at time t + 1, or in other words, how the influence spreads through the graph G = (V, E). Given a difusion model, the influence maximization problem aims to ifnd the best initial set of k nodes which have the maximum expected influence at the end of the difusion process. The function σ(S) denotes the expected number of nodes influenced at the end of the difusion process.
A hypergraph is a generalization of a graph, where the hyperedges are subsets of vertices (rather than just pairs). More formally, a hypergraph H = (V, E) has a set of vertices V , and every e ∈ E is such that e ⊆ V .
It is not always possible to represent the relationships between actors (nodes/vertices) through the edge, which is a pairwise (dyadic) relation. For instance, in a research setting, researchers collaborate in small groups to write scientific publications.
Copyright © 2016 for the individual papers by the papers’ authors. Copying permitted
for private and academic purposes. This volume is published and copyrighted by its
editors.
Co-membership of a group in such a setting becomes a super-dyadic relation. A
co-authorship network (e.g the arXiv Astrophysics co-authorship network [
The problem of influence maximization in a hypergraph has remained hitherto
unexplored. [
HEMI: Hyperedge Majority Influence Maximization Moreover, the influence maximization experiments are performed on a clique reduction of a hypergraph rather than the exact hypergraph representation. Hence, the authors simply use existing difusion models for simple graphs such as IC and LT. Hence, to the best of our knowledge, there are no difusion models defined which directly model the spread of influence on a hypergraph. Our first motivation, hence is to define a difusion model for hypergraphs, and analyze whether it is submodular.
In a hypergraph, the nodes represent actors while the hyperedges could be thought of as representing groups or afiliations. At the end of a difusion process, every hyperedge could have some influenced incident nodes and some non-influenced incident nodes. One may seek to extend the notion of a node being influenced to a afiliation (hyperedge) being influenced. A afiliation is considered influenced if a majority of its nodes (members) are influenced at the end of the difusion process. There may exist situations where one seeks to maximize the number of afiliations influenced rather than the number of nodes influenced.
For instance, consider a political campaign on a social network such as Facebook, where the hyperedges correspond to Facebook groups while the nodes correspond to Facebook users. By controlling or influencing a Facebook group, one can dominate the content on the group’s page. However, one cannot directly influence an afiliation, since the mechanism of influence propagation takes place through users getting converted in support of the political campaign. The manager of the political campaign here would be interested in selecting the set of initial users (who can be made to support the campaign through promotions or other incentives) which would maximize the number of groups influenced. This is a distinct objective from maximizing the number of nodes influenced, as we shall illustrate now through an example. We refer to this new variant of influence maximization as HEMI (Hyperedge Majority Influence Maximization). σHEMI (S) is the expected number of hyperedges a majority of whose nodes are influenced at the end of the difusion process.
Consider a hypergraph H where the hyperedges are e1 = {v1, v2, v3}, e2 = {v3, v4, v6}, e3 = {v3, v5, v7}. Maximizing the number of nodes would not distinguish between the case where S1 = {v1, v2, v3} and S2 = {v3, v4, v5} are the final set of nodes influenced, since σ() = 3. However, σHEMI () = 1 in the first case and 2 in the second.
An added motivation of solving HEMI rather than maximizing the number
of nodes directly would be the diversification it achieves. Attaining diversity for
problems such as graph centrality based ranking [
The rest of this paper is organized as follows - 3 states the definition of the influence maximization problem, and other related preliminaries. 4 explains the proof for submodularity of the Independent Cascade Model. 5 describes the difusion model on hypergraphs which we have used later. 6 proves that the difusion model is submodular. 7 formally define the HEMI problem. 8 proves that HEMI is not submodular. 9 states possible directions for further work on this problem. 3
The Independent Cascade Model is a well-known difusion model. Under this
model, a node u which is influenced at time t gets one opportunity to influence
each of its neighbors v with probability pu,v for time step t + 1. The probability
pu,v is either set to a small constant (e.g 0.1) or set to k1v , where v is the target
node and kv is its degree. Another well-known difusion model is the Linear
Threshold (LT) model, where every node v first randomly chooses a threshold
αv ∈ [
The major contribution of [
σ(S ∪ v) − σ(S) ≥ σ(T ∪ v) − σ(T ) (1)
As a result of this observation, the question of whether a difusion model is submodular or not acquires special importance (most difusion models tend to be monotone anyway), since this allows the use of the greedy algorithm with an approximation guarantee. The authors then went onto prove that both the IC and LT difusion models were submodular, i.e they had a submodular σ() function. In section 4, we revisit the proof of submodularity for the IC model, since it is relevant for understanding the proof for submodularity (and counterexample for non-submodularity), which we present later on. 4
In the IC model, an edge (u, v) is used in the difusion process with probability pu,v. Instead of determining whether (u, v) is used at the time of difusion, one
HEMI: Hyperedge Majority Influence Maximization can perform a trial with respect to each edge (u, v), and form a set of live edges X ⊆ E. Only these live edges participate in the difusion process. We denote by σX (S) the number of nodes influenced given the initial set S and the live edge set S. Note that once the live edges are fixed, there is no randomness in the process. Now, one can easily see that σX (S) is simply the size of the set of nodes reachable from S under the graph GX = (V, X). Since reachability is submodular. Our difusion model is a simple generalization of the Independent Cascade Model to hypergraphs. Here, we consider a graph Gaug = (V ∪ E, Eaug), where the set of nodes Vaug is the union of the set of nodes and the set of hyperedges. An edge eaug = (v, e) or (e, v) ∈ Eaug if v ∈ V, e ∈ Ev ∈ e. For a node-hyperedge pair (v, e) such that v ∈ e, we add edges in both directions ((e, v) and (v, e)). This allows us to have independent probabilities of the influence flowing in either direction. In our model, the hyperedges act as carriers of the influence, allowing it to flow from one node to another through them. However, note that in the HEMI objective, we include a hyperedge only if a majority of its nodes are influenced, regardless of whether it has acted as a carrier.
A node v which is influenced at time step t can influence an incident hyperedge e with probability pv,e for time step t + 1 through the edge (v, e). A hyperedge e which is influenced at time step t can influence an incident node v with probability pe,v for time step t + 1 through the edge (e, v). Though the probabilities pe,v and pv,e could be set in any way, we use the following two schemes for setting them – pe,v = p1 and pv,e = p2 ∀v ∈ V , e ∈ E, v ∈ e. Here p1 and p2 are constants.
This is similar to the scheme used in [
Note that our difusion model does not simplify to a difusion model on some simple graph reduction of the hypergraph. To understand why this is the case, consider the hypergraph H in Figure 2 where a hyperedge e has 4 nodes u, v, z and w incident on it. Also, u, v, w and z do not have any other hyperedges incident on them.
Varun Gangal, Balaraman Ravindran, and Ramasuri Narayanam Suppose w is already influenced. Now, note that the hyperedge e will get influenced (as a carrier) with probability 0.5. Let Xe denote the 0-1 random variable, which is 1 if e is influenced, and 0 otherwise. Similarly, let Xu, Xv, Xz and Xw be the 0-1 random variables corresponding to whether the respective node is influenced or not. Xu, Xv and Xz are conditionally independent given Xe. We can see this from the fact that P (Xu|Xe, Xw = 1) = P (Xu|Xv, Xe, Xw = 1) = 0.5. Symmetrically, this holds for the other pairs.
However, they are not conditionally independent given only Xw. We can see that P (Xu|Xw = 1) = P (Xu|Xe = 1)P (Xe = 1|Xw = 1) = 0.5 × 0.5 = 0.25. Let us now find the value of P (Xu|Xw = 1, Xv = 1).
P(Xu = 1|Xw = 1, Xv = 1) = P(Xu = 1|Xe = 1)P(Xe = 1|Xw = 1, Xv = 1) = 0.5 P(Xv = 1|Xe = 1)P(Xe = 1|Xw = 1)
P(Xv = 1|Xw = 1) = 0.5 P(Xv = 1|Xe = 1)P(Xe = 1|Xw = 1)
P(Xv = 1|Xw = 1)
Since P (Xu|Xw = 1, Xv = 1) > P (Xu|Xw = 1), we can see that Xu and Xv are
not conditionally independent given only Xw. A simple graph based
representation, with the IC difusion model will not be able to model the dependence
between Xu and Xv, given Xw at time t. This is because the state of Xu and Xv
at the next time step (t+1), only depends on whether the respective edges (w, u)
and (w, v) become live. The triadic relation captured by the hyperedge between
w, u and v is not captured here. [
HEMI: Hyperedge Majority Influence Maximization 6
We shall first prove that the function σ(S) where S is the number of initially influenced nodes and σ(S) is the final number of nodes influenced, is submodular under our difusion model. Our proof is a simple generalization of the proof for submodularity of Independent Cascade in simple graphs.
Consider the graph Gaug. Assume, as in the original IC proof, that the set of live edges X is decided by performing all the trials prior to the difusion process. Consider sets of nodes in the original hypergraph S ⊆ V, T ⊆ V, S ⊂ T , and a node in the original hypergraph v ∈/ T . Now, σ(S) is the set of augmented graph nodes which were nodes in the original graph and are reachable from the set S in the augmented graph. Note that this does not include the augmented graph nodes which correspond to hyperedges, though the paths which are used to reach a node v ∈ V from u ∈ S may have hyperedges as intermediate nodes.
Using the same argument as in the KKT proof, since reachability is submodular, we get
σX (S ∪ v) − σX (S) ≥ σX (T ∪ v) − σX (T ) Taking the expectation over all X, σ(S ∪ v) − σ(S) ≥ σ(T ∪ v) − σ(T ) (9) (10) 7
Consider the state of the hypergraph H = (V, E) at the end of a trial of the difusion process, for a given initial set S. Some of the nodes will be influenced, and some will not be influenced. Let the set of influenced nodes be I. The set of non-influenced nodes will be V − I. Clearly σ(S), the expected number of nodes influenced, is equal to E[|I|].
Let Ve denote the set of nodes incident on a given hyperedge e. For HEMI, we are interested in the number of hyperedges, a majority of whose nodes are influenced. We define Y to be this set. More formally,
Y = {e ∈ E|Ve ∩ I ≥ |V2e| + 1} (11) Now, σHEMI (S) = E[|Y |].
Varun Gangal, Balaraman Ravindran, and Ramasuri Narayanam 8
Consider the hypergraph H shown in Figure 3. H has hyperedges e1 = {v1, v2, v4}, e2 = {v1, v2, v3, v5, v6}, e3 = {v2, v3, v4}. The augmented graph Gaug will have 2 × (3 + 5 + 3) = 22 edges. Let σHEMI (S) be the number of hyperedges with a majority of their nodes influenced at the end of the difusion process. Let σXHEMI (S) be the number of majority-influenced hyperedges given a set of live edges X in the augmented graph. One can exactly compute σ(S) by enumerating over all possible live sets X. where P(X) is given by σHEMI (S) = X P (X)σXHEMI (S)
X P (X) = Πeaug∈X p(eaug) (12) (13) Here p(eaug) = pe,v or pv,e depending on the directionality of the edge i.e whether it goes from a node to a hyperedge or in the reverse direction. However, note that using this method of enumerating outcomes even for this small example, would require us to enumerate 222 outcomes. Instead, we find an estimate of σHEMI (S) using a simulation-based method.
Consider the sets S = {v5}, T = {v1, v3, v5} and v = v2. Now, we run simulations to estimate σH (S), σH (S ∪ v), σH (S ∪ v) and σH (T ∪ v). For a given set, we run 105 trials. In each trial, we start with the initial set influenced at
HEMI: Hyperedge Majority Influence Maximization time step 0, and then run the difusion model until convergence (set of influenced nodes stops growing). We then find the number of hyperedges a majority of whose nodes are influenced. We find this number averaged over all the trials.
We can see that submodularity is violated for a wide range of p1 and p2 values. The intuition here is that node v2, which is incident on all the hyperedges, can act as a swing vertex (converting a non-majority into a majority) only when one less than majority of the nodes in a hyperedge it belongs to are influenced. A larger initial set helps having more influenced nodes in the end, thus helping v perform the role of converting a non-majority into a majority in more hyperedges. Hence, a larger initial set results in a larger marginal gain on adding v to the initial set.
The threshold values are chosen with the intuition that the probability of
spreading is a small value less than 0.5. In the original influence maximization
paper [
Thus, we can see that the HEMI objective σHEMI (S) is non-submodular. This means the greedy algorithm is no longer guaranteed to provide a (1 − 1e ) approximation. 9
Although we have proved that the HEMI objective is non-submodular, we are yet to devise an algorithm which can solve the problem with some provable guarantee. Devising such an algorithm is a point of future interest. One possible direction could be to formulate the HEMI objective as a diference of two submodular functions, or having submodular upper and lower bounds.