Influence Maximization in Hypergraphs

A hypergraph is represented as $H(V,E)$, in which $V=\{v_{1},v_{2},...,v_{n}\}$ is the node set and $E=\{e_{1},e_{2},...,e_{m}\}$ is the hyperedge set. An incidence matrix of $H$ is given by $C=(c_{i\alpha})_{[n\times m]}$, where

Therefore, the adjacency matrix $A_{[n\times n]}$ can be derived from $C$,

where $D$ is a diagonal matrix whose diagonal elements represent the number of hyperedges a node belongs to. The value of $A_{ij}$ indicates the number of hyperedges that contain both node $v_{i}$ and node $v_{j}$. An example of a hypergraph is given in Figure 1, which contains 5 nodes and 2 hyperedges. The incidence matrix $C$ and adjacency matrix $A$ are also given correspondingly.

Given the incidence matrix of a hypergraph, we can define the degree of a node in a hypergraph in two different ways [27], i.e., the degree and the hyperdegree. The degree of a node $v_{i}$ ($deg(i)$) indicates the number of neighboring nodes that $v_{i}$ is adjacent to, which can be expressed as follows:

where

The hyperdegree of node $v_{i}$ is defined as the number of hyperedges that node $v_{i}$ belongs to, which is given by the following equation:

According to the above definitions, we can calculate the degree and hyperdegree of the nodes in Figure 1. For instance, the degree of node $v_{3}$ is $deg(3)=4$ and the hyperdegree of node $v_{3}$ is $d^{H}(3)=2$.

We show the basic description and properties of eight hypergraphs generated by real-world datasets, which are collected from different domains¹¹1https://www.cs.cornell.edu/~arb/data/ ²²2http://bigg.ucsd.edu/. The hypergraphs will be used to evaluate the performance of our algorithms in the subsequent sections. The topological properties of them are given in Table 1. The detailed description of each data is given as follows:

cat-edge-algebra-questions dataset (Algebra) & cat-edge-geometry-questions dataset (Geometry). The two datasets contain interactions between users on the stack exchange web site Math Overflow. The interactions between users are mainly about comments, questions and answers on algebra (or geometry) problems. Each node represents a user on MathOverflow and hyperedges are sets of users who answered a certain question category (algebra or geometry).

cat-edge-madison-restaurant-reviews (Restaurant-Rev). The data indicates users who reviewed an establishment of a particular category (different types of restaurants in Madison, WI) within a month timeframe. Each node represents a user on Yelp and a hyperedge represents a set of users who reviewed a certain restaurant.

cat-edge-music-blues-reviews (Music-Rev). The data contains nodes representing users on Amazon, and hyperedges are sets of reviewers who reviewed a certain product category (different types of blues music) within a month timeframe.

cat-edge-vegas-bars-reviews (Bars-Rev). Each node in the dataset represents a user on Yelp, and a hyperedge is a set of users who reviewed a certain bar in Las Vegas, NV.

NDC-classes. The dataset contains nodes representing class labels, and a hyperedge is a drug which consists of a set of class labels.

iAF1260b. The data contains nodes representing reaction-based metabolics, and hyperedges are sets of metabolics which are applied to a certain reaction. The duplicate hyperedges are removed.

iJO1366. Similar to iAF1260b, this is also a metabolic hypergraph with each node representing a reaction-based metabolic, and hyperedges are sets of metabolics which are applied to a certain reaction. The duplicate hyperedges are removed.

Given a specific spreading model, the influence maximization problem[28] aims to identify $K$ spreaders (also called seed nodes) in a network that can maximize the expected number of influenced nodes. Mathematically, the problem can be described as follows,

where $\sigma(S)$ represents the expected influence of the seed node set $S$, and the number of nodes $K$ in the seed set is the constraint condition of this problem.

It has been shown that the influence maximization problem in ordinary networks is NP-hard [6]. And the influence maximization problem in hypergraphs, which can be considered as the generalization of influence maximization in ordinary networks, is also NP hard [21]. That is to say, it cannot be solved in polynomial time. Therefore, we propose to use greedy and heuristic algorithms to approximate its optimal solution.

To quantify the spreading influence of the seed nodes [29, 30], we propose to use a Susceptible-Infected (SI) model with Contact Process (CP) dynamics on a hypergraph [26, 31]. In the model, an individual can only take one of the two states, i.e., susceptible (S) or infected (I). An S-state node can be infected by each of its I-state neighbors with infection probability $\beta$. The model is described as follows:

(i) Initially, nodes in the seed set are set to be I-state and the rest nodes are in S-state.

(ii) At each time step $t$, we first find the I-state nodes. For each I-state node $v_{i}$, we find all the hyperedges $E_{i}=\{e_{i1},e_{i2},\cdots,e_{iq}\}$ that node $v_{i}$ belongs to. Then a hyperedge $e$ is chosen from $E_{i}$ uniformly at random. For each of the S-state nodes in $e$, it will be infected by node $v_{i}$ with infection probability $\beta$.

(iii) We terminate the process until a specific time step $T$ reaches, where $T$ is a control parameter.

We show an illustrative example of the spreading process in Figure 2. At time step $t=1$, node $v_{8}$ is in I-state. The hyperedge set that contains $v_{8}$ is $E_{3}=\{e_{3},e_{4},e_{5}\}$. At time step $t=2$, the S-state nodes, i.e., $v_{3}$ and $v_{4}$ in hyperedge $e_{3}$, are infected by node $v_{8}$. Subsequently, the I-state nodes $v_{3}$, $v_{4}$ and $v_{8}$ infect the S-state nodes in hyperedges $e_{1},e_{2},e_{4}$.

Given nodes $v_{i}$ and $v_{j}$, we suppose that the influenced node sets at time step $T$ by setting node $v_{i}$ and $v_{j}$ as the seed node are given by $I_{T}(v_{i})$ and $I_{T}(v_{j})$, respectively. Thus, the influence overlap $o_{ij}^{T}$ at time step $T$ between $v_{i}$ and $v_{j}$ can be defined as $o_{ij}^{T}=\frac{I_{T}(v_{i})\cap I_{T}(v_{j})}{n}$. In Figure 3, we show the comparison between the influence overlap distribution of a neighboring node pair and a randomly selected node pair in various hypergraphs. In most of the datasets (i.e., Figure 3(a), (b), (e), (g) and (h)), the probability that a neighboring node pair have overlapped influence is always higher than that of a randomly selected node pair. It suggests that when we choose one node as the seed, the probability that its neighboring nodes are choosing as the seed should be lower to avoid overlapped influence. Based on this assumption, we propose an adaptive degree-based heuristic algorithm, i.e., Heuristic Degree Discount (HDD), to solve the influence maximization problem.

Heuristic Degree Discount (HDD). In HDD, we aim to punish nodes that have more neighbors in $S$ in each iteration. The details of HDD is shown in Algorithm 1. To conduct the algorithm, we first give the original degree vector of all the nodes as $deg^{0}=(deg^{0}(1),deg^{0}(2),\cdots,deg^{0}(n))$.

(i) At the initial step, a node $v_{i}$ that has the largest degree is chosen, i.e., $deg^{0}(i)=\max\left\{deg^{0}\right\}$, and added to the seed set $S$. For every neighboring node $v_{u}$ of $v_{i}$, we first find the neighbors of $v_{u}$ in $S$ and collect them as a set $N_{S}(u)$. Then the adaptive degree of node $v_{u}$ is updated as $deg^{1}(u)=deg^{0}(u)-Z$, where $Z=|N_{S}(u)|$ is the number of elements in $N_{S}(u)$. For the other nodes that are not the neighbors of $v_{i}$, e.g., node $v_{w}$, $deg^{1}(w)=deg^{0}(w)$. After updating the adaptive degree of every node, we obtain an adaptive degree vector $deg^{1}=(deg^{1}(1),deg^{1}(2),\cdots,deg^{1}(n))$.

(ii) At step $k$, the node that has the largest adaptive degree (denoted as $v_{j}(v_{j}\in V\backslash S)$), i.e., $deg^{k-1}(j)=\max\{deg^{k-1}\}$, is chosen, and we add it to the seed set $S$. For every neighboring node $v_{q}$ of $v_{j}$, we first find the neighbors of $v_{q}$ in $S$ and collect them as a set $N_{S}(q)$. The adaptive degree of $v_{q}$ is further updated by $deg^{k}(q)=deg^{k-1}(q)-Z$, where $Z=|N_{S}(q)|$ is the number of elements in $N_{S}(q)$. For the other nodes that are not the neighbors of $v_{j}$, e.g., node $v_{w}$, $deg^{k}(w)=deg^{k-1}(w)$. We obtain a new adaptive degree vector as $deg^{k}=(deg^{k}(1),deg^{k}(2),\cdots,deg^{k}(n))$ after updating the adaptive degree of every node.

(iii) The algorithm is terminated when we obtain $K$ seed nodes.

We propose a simplified algorithm which considers to give an even penalty for every node in the iteration, i.e., at step $k$, the adaptive degree of $v_{q}$ is further updated by $deg^{k}(q)=deg^{k-1}(q)-Z$, where $Z=1$. The simplified algorithm is named as Heuristic Single Discount (HSD), which we will use as a baseline for comparison. We show the details of HSD in Algorithm 2.

To verify the performance of our algorithms, we propose two algorithms extended from ordinary network, i.e., H-RIS and H-CI, and choose state-of-the-art algorithms, i.e., Greedy, Hyperdegree, Degree, proposed by other researchers as baselines. The details of each algorithm are given as follows.

Hyper Reverse Influence Sampling (H-RIS). Reverse Influence Sampling (RIS) algorithm was proposed to solve the influence maximization problem in an ordinary network [32]. In this work, we propose to extend the reverse influence sampling algorithm to a hypergraph by first introducing the following two definitions:

Based on the above definitions, we illustrate the details of the H-RIS algorithm in Algorithm 3, which mainly contains the following two steps:

(i) We generate $\eta$ random HRR sets, in which $\eta$ is a tunable parameter.

(ii) In each round of seed selection, we add node $v_{q}$ with the highest frequency in the generated HRR sets to the seed set $S$. Then, the HRR sets that contain node $v_{q}$ are removed. The selection rounds will be terminated until $K$ seed nodes are selected.

The algorithm suggests that if a node appears more frequently in different HRR sets, it will have a higher probability to influence the other nodes. Correspondingly, the more HRR sets that the seed set $S$ covers, the more likely that $S$ will have a large expected influence. We set $\eta=200$ to conduct the experiments.

Hyper Collective Influence (H-CI). Collective Influence (CI) was first proposed to select seed nodes based on the degree of distant nodes in an ordinary network [33] . We extend the algorithm to a hypergraph by simply replacing node degree by the hyperdegree in the definition of hyper collective influence. A ball $Ball(v_{i},l)$ is defined as a set of nodes which contains nodes inside a ball of radius $l$, where $l$ denotes as the shortest path from a node in $Ball(v_{i},l)$ to node $v_{i}$. $\partial Ball(v_{i},l)$ is the frontier of $Ball(v_{i},l)$, i.e., the path length of any node inside $\partial Ball(v_{i},l)$ to node $v_{i}$ equals to $l$. We define the HCI of node $v_{i}$, which is read as

where $d^{H}(i)$ is the hyperdegree of node $v_{i}$.

Given a specific value of $l$, we calculate the HCI of every node in the hypergraph and choose top $K$ nodes that have the highest HCI value as the seeds for influence maximization problem. In this work, the tunable parameter $l$ is set as $1$ and $2$, and we name the algorithms as H-CI$(l=1)$ and H-CI$(l=2)$, respectively.

Greedy. Greedy algorithm gives a guaranteed approximation of influence spread by accurately approximating influence spread with high computational complexity. The algorithm can be extended to a hypergraph [6], which is shown in Algorithm 4. We denote $S_{k-1}$ as the seed nodes that are selected at round $k-1$, the expected influence spread by $S_{k-1}$ is given by $\sigma(S_{k-1})$. The marginal influence spread by adding node $v$ to the seed set at round $k$ is given by $\sigma(S_{k-1}\cup\left\{v\right\})-\sigma(S_{k-1})$. At the beginning of the algorithm, $S$ is set to be empty. At round $k$, we calculate the expected influence spread $\sigma(S_{k-1}\cup\left\{v\right\})$ for each $v$, where $v\in V\backslash S_{k-1}$. Node $v_{k}$ with the largest marginal influence contribution ($v_{k}=\arg\max_{v\notin S_{k-1}}\left\{\sigma(S_{k-1}\cup\left\{v\right\})-\sigma(S_{k-1}\right\}$) is added to the seed set , i.e., $S_{k}=S_{k-1}\cup\left\{v_{k}\right\}$. The algorithm is terminated until $K$ seed nodes are selected.

HyperDegree. We compute the hyperdegree of every node in a hypergraph and choose top $K$ nodes with the highest hyperdegree as the seeds for influence maximization problem.

Degree. Similar to HyperDegree, we calculate the degree of every node in a hypergraph and select top $K$ nodes with the highest degree into the seed set $S$ for influence maximization problem.