A hyper-distance-based method for hypernetwork comparison

A hypernetwork is defined as $H=(V,E)$, with sets of nodes $V$ and hyperedges $E$ represented as $V=\{v_{1},v_{2},\cdots,v_{N}\}$ and $E=\{e_{1},e_{2},\cdots,e_{M}\}$, respectively, where $N$ and $M$ represent the number of nodes and hyperedges. An incident matrix $I_{N*M}$ is constructed based on the membership relationship between the nodes and hyperedges. If node $v_{i}$ is part of a hyperedge $e_{j}$, then the value of $I_{ij}$ is set to $1$, otherwise it is $0$. Therefore, we can obtain the following.

where $k(v_{i})$ and $k^{E}(e_{j})$ represent the hyperdegree of node $v_{i}$ and the size of hyperedge $e_{j}$, respectively.

We create the ordinary network $G=(V,E^{o})$ of $H$ by linking all the nodes that are part of a hyperedge in $H$. In other words, an edge $e^{o}=(v_{i},v_{j})\in E^{o}$ if $v_{i}$ and $v_{j}$ both appear in at least one of the hyperedges in $E$. The network $G$ is an unweighted and undirected network, and its adjacency matrix is denoted as $A^{o}$. This means that if there is an edge between the nodes $v_{i}$ and $v_{j}$ in $G$, then $A^{o}_{ij}$ is equal to 1, otherwise it is 0.

The $s$-distance between nodes: We employ the hyperedge distance from [21] to calculate the $s$-distance between two nodes. Two hyperedges are considered to be $s$-adjacent if they have at least $s$ nodes in common. Concretely, the $s$-distance between two hyperedges, $e_{i}$ and $e_{j}$, is denoted as $L_{s}^{E}(e_{i},e_{j})$ and is expressed as:

Based on the above definition, the $s$-distance between two nodes $v_{i}$ and $v_{j}$ is $L_{s}^{V}(v_{i},v_{j})$ and can be defined as follows:

The $s$-distance distribution of a hypernetwork: The proportion of nodes whose $s$-distance from node $v_{i}$ is denoted by $p_{i}^{s}(j)$. The $s$-distance distribution of node $v_{i}$ is represented by a vector of size $1\times(d^{s}+1)$, denoted as $P_{i}^{s}=\{p_{i}^{s}(j)\}$, where $d^{s}$ is the maximum value of $s$-distance. The proportion of nodes that have an $s$-distance of infinity from node $v_{i}$ is represented by $p_{i}^{s}(d^{s}+1)$. Consequently, we define the $s$-distance distribution of the hypernetwork $H$ as $P^{s}=\{P_{1}^{s},P_{2}^{s},\cdots,P_{N}^{s}\}$, indicating the detailed topological information with respect to the $s$-distance between nodes. When $s=1$, the distance distribution of the ordinary network is obtained, which is derived by $H$, is obtained; when $s>1$, a high-order distance distribution is revealed, which reflects the various high-order topological relationships between nodes that are indicated by different values of $s$. It should be noted that for a hypernetwork $H$, we have $1\leq s\leq S_{m}$, where $S_{m}$ represents the maximum number of overlapping nodes between hyperedges.

Dissimilarity between two hypernetworks: Given a hypernetwork $H$ and its $s$-distance distribution $P^{s}=\{P_{1}^{s},P_{2}^{s},\cdots,P_{N}^{s}\}(1\leq s\leq S_{m})$, we leverage the Jensen-Shannon divergence to define the $s$-order heterogeneity, which is named $s$-order hypernetwork node dispersion $NND^{s}(H)$. The definition of $NND^{s}$ can be expressed as follows:

where $J(P_{1}^{s},P_{2}^{s},\cdots,P_{N}^{s})$ represents the Jensen-Shannon divergence of nodes $s$-distance distribution, and is defined as:

where ${\mu}_{j}^{s}$ denotes the average of the $N$ $s$-distance distributions, which is given by:

We compare the dissimilarity between two hypernetworks, i.e., $H$ and $H^{{}^{\prime}}$, based on the $s$-order heterogeneity defined above. Specifically, the structural dissimilarity $D(H,H^{{}^{\prime}})$ is written as follows:

where $J(\mu_{H}^{s},\mu_{H^{\prime}}^{s})$ denotes the Jensen-Shannon divergence of the average $s$-distance distributions between $H$ and $H^{{}^{\prime}}$. Dissimilarity $D(H,H^{{}^{\prime}})$ is composed of two terms: The first term compares the average connectivity of nodes at different $s$-distances, capturing global dissimilarity between two hypernetworks; The second term integrates the dissimilarities among different network node dispersions via varying the value of $s$, indicating the local differences between two hypernetworks. We use a parameter $\beta(0<\beta<1)$ to adjust the importance of these two terms. A higher value of $D(H,H^{{}^{\prime}})$ indicates larger differences between $H$ and $H^{{}^{\prime}}$.

For clarity, we give a flow diagram of the proposed hypernetwork comparison method in Figure 1. Taking a hypernetwork $H$ as an example, we first compute the $s$-distance distribution ($P^{1},P^{2},\cdots,{P^{S_{m}}}$). Subsequently, the values of $NND^{s}(H)$ and $\mu_{H}^{s}$ are calculated using Eqs. (5-7). Consequently, the values of $NND^{s}(H^{{}^{\prime}})$ and $\mu_{H^{{}^{\prime}}}^{s}$ can also be computed. We further obtain the dissimilarity between $H$ and $H^{{}^{\prime}}$ following Eq. (8).

For a given value of $s$, the s-distance-based hypernetwork portrait $B^{s}$ is an array with $(l,k)$ elements [12, 22], and we have

where $0\leq{l}\leq{d^{s}}$, $0\leq{k}\leq{N-1}$, and $d^{s}$ denotes the maximum $s$-distance value. It is noteworthy that the hypernetwork portrait $B^{s}$ is independent of the ordering or labeling of nodes. We use probability distribution $Q^{s}$ to comprehend the entries of $B^{S}$. Thus, the probability of a randomly selected node having $k$ nodes at a distance of $l$ is expressed by

We consider two hypernetworks, $H$ and $H^{{}^{\prime}}$, and use $Q^{s}$ and $Q^{s^{\prime}}$ as probability distributions to interpret the rows of the $s$-distance-based hypernetwork portraits for each of them. The difference between $H$ and $H^{{}^{\prime}}$ is expressed by $D^{P}(H,H^{\prime})$ and is stated as:

where $M^{s}=\frac{1}{2}(Q^{s}+Q^{s^{\prime}})$, $KL(\cdotp|\cdotp)$ is the Kullback-Liebler divergence [23] between the two distributions. We compare the difference between $H$ and $H^{{}^{\prime}}$ by comparing the difference of the portrait distributions of every order of distance with the alteration of $s$.

The adjacency tensor of a hypernetwork $H$ is indicated by $T\in\mathbb{R}^{\xi\times{N}\times{N}}$ [24, 25, 26], where $\xi$ is the maximum size of the hyperedges and $N$ is the number of nodes. If nodes $v_{i}$ and $v_{j}$ are both present in a hyperedge of size $k$, then $T_{kij}$ is set to 1; if not, it is 0. Subsequently, we use the adjacency tensor $T$ to compare the similarity between two hypernetworks $H$ and $H^{\prime}$, which is represented as follows:

where $\gamma$ is a parameter that can be tuned, and we choose $\gamma=2$ in the subsequent experiments.

To perform hypernetwork comparisons, we construct centrality vectors for nodes or hyperedges based on various centrality measures. The centrality of each node or hyperedge is denoted by $c=(c_{1},c_{2},\dots,c_{N})^{T}$ or $c=(c_{1},c_{2},\dots,c_{M})^{T}$ respectively, with $N$ and $M$ being the total number of nodes and hyperedges. The formula to compare two hypernetworks $H,H^{{}^{\prime}}$ using node centrality methods can be written as:

and the formula for comparing $H,H^{{}^{\prime}}$ using hyperedge centrality methods is given by

We utilize six centrality measures  [2, 27, 21, 28, 29, 30], including node centrality methods such as Hyper Degree Centrality (HDC), Normalized Degree Centrality (NDC), Vector Centrality (VC) and three hyperedge centrality methods, s-Eccentricity Centrality (ECC), Edge-base Degree Centrality (EDC), s-Harmonic Closeness Centrality (HCC), to compare hypernetworks. Centrality measures are employed to create centrality vectors for nodes or hyperedges, which are then used as characteristics for the comparison of hypernetworks.

We evaluate the performance of our approach by contrasting the synthetic uniform hypernetworks created by the Erdos-Rényi hypernetwork model [20], Watts-Strogats hypernetwork model (WSH) [31], and the Scale-Free hypernetwork model (SFH) [32, 33]. Details of how to generate synthetic hypernetworks are given below:

Erdos-Rényi hypernetwork model (ERH). The ERH model constructs a $k^{E}$-uniform hypernetwork $H=(V,E)$ given the number of nodes $N$ and the number of hyperedges $M$. Specifically, we first randomly select $k^{E}$ nodes to form a hyperedge $e$ and add $e$ to $E$ if $e\notin E$, otherwise we reselect the nodes. We repeat the above process for $M$ times to obtain $H$.

Watts-Strogats hypernetwork model (WSH). The WSH model generates the $k^{E}$-uniform WS hypernetwork given the number of nodes $N$ and rewiring probability $q$. The model is described as follows: Initially, a $k^{E}$-ring hypernetwork $H=\{N,E\}$ is given, where all nodes are arranged in a circular manner, and each node forms two hyperedges with its $k^{E}-1$ left and right nodes separately. For each hyperedge $e$, we randomly select $k^{E}$ nodes to form a new hyperedge $e^{{}^{\prime}}$. If $e^{{}^{\prime}}\notin E$, we replace $e$ by $e^{{}^{\prime}}$ with probability $q$. The process will be terminated until all the hyperedges in $H$ are traversed.

Scale-free hypernetwork model (SFH). Given the number of nodes $N$, the number of hyperedges $M$ and the degree distribution $p(k)\sim(k)^{-r}$, we generate a $k^{E}$-uniform SFH hypernetwork through the following steps: (i) we create a node degree sequence based on the degree distribution $p(k)\sim(k)^{-r}$, and each node $v_{i}$ is assigned a probability $p_{i}$ according to the node degree sequence; (ii) For an empty hyperedge $e$, we add node $v_{i}$ to $e$ with probability $p_{i}$ until the hyperedge size of $e$ reaches $k^{E}$. If $e$ already exists in $H$, we regenerate $e$; (iii) Repeat step (ii) for $M$ times.

The results of comparing uniform hypernetworks generated by ERH for various methods are depicted in Figure 2, with $k^{E}$ representing the size of hyperedges. For HD, we observe that hypernetworks are similar when the values of $k^{E}$ are close, which is in agreement with the way the hypernetworks are generated. The other baseline methods (except Portrait and ECC) show similar trends with those of HD with different values, indicating that the majority of the methods can distinguish hypernetworks generated by ERH with different $k^{E}$. We analyze the hypernetworks created by WSH and compare them in Figure 3 based on different rewiring probabilities $q$. The results demonstrate that HD, Tensors, EDC, HCC, and NDC are capable of distinguishing hypernetworks created by different $q$ values. On the other hand, the other methods cannot. For instance, the dissimilarity between networks generated by $q=0.1$ and $q=0.5$ and networks generated by $q=0.3$ and $q=0.5$ are roughly the same, which is counter-intuitive. For the uniform hypernetworks generated by SFH, we show the difference between networks generated by different values of $r$ (see Figure 4), which is the slope of the degree distribution. It can be intuitively assumed that hypernetworks should be alike when the value of $r$ is near, and HD can demonstrate this pattern. In contrast, the other baselines are unable to distinguish between hypernetworks created with different $r$ values. Overall speaking, HD is robust to distinguish hypernetworks generated by different models, but the baselines have weakness in different scenarios.

We further explore whether our method can classify hypernetworks generated by different mechanisms and the results are given in Figure 5. We generate ERHs, WSHs, and SFHs with a network size of $N=1000$. For each type, we generate $30$ hypernetworks. The similarities between the hypernetworks are calculated by HD, and we further adopt multidimensional scaling map to show the distance between them in a geometric space. A shorter distance indicates that the two hypernetworks are more similar. The results of our analysis demonstrate that HD is effective in classifying hypernetworks, as those generated by the same mechanism are grouped together and those generated by different mechanisms are separated.

We use six hypernetworks created from empirical data to prove the efficiency of our approach. Yuecai and Chuancai are recipe hypernetworks in which the hyperedges are made up of the components of each dish. Restaurants-Rev and Bar-Rev are review hypernetworks obtained from Yelp.com. These hypernetworks are composed of users who have reviewed the same restaurant or bar. NDC-classes is a hypernetwork of drugs, with each hyperedge representing a combination of class labels that make up a single drug. Algebra is collected from MathOverflow.net, where users who answered the same question are enclosed in a hyperedge. The information regarding the topological characteristics of the hypernetworks is presented in Table 1. This table includes the number of nodes, the number of hyperedges, the degree, the average hyperdegree, the average size of the hyperedges, the clustering coefficient, the average shortest path length, the diameter, and the average link density of each hypernetwork. It is worth noting that the clustering coefficient, the average shortest path length, the diameter, and the average link density are computed based on the ordinary networks of the hypernetworks.

We assess the effectiveness of our proposed technique by performing hyperedge perturbations on empirical hypernetworks. We randomly add or take away a certain proportion ($f\in[-0.9,0.9]$) of hyperedges from a hypernetwork. A positive value of $f$ indicates the addition of hyperedges, while a negative value implies the deletion of hyperedges. The size of each added hyperedge is randomly chosen from the range of $[2,\xi]$, where $\xi$ is the maximum hyperedge size. We compare the difference between the original hypernetwork and the perturbed hypernetworks, the results are shown in Figure 6. The proposed method, i.e., HD, exhibits a good increasing trend of the dissimilarity values in both hyperedge deletion and addition perturbations in all the empirical hypernetworks. It follows that if we make more changes to the number of hyperedges in the hypernetwork, the resulting hypernetworks will be more different from the original one, which is in line with our expectations. In contrast, baseline methods are inferior to HD. For example, the portrait method shows a clear decreasing trend of dissimilarity values in hyperedge deletion for hypernetworks such as Yuecai, Chuancai, and Algebra, which means if we delete more hyperedges from a hypernetwork, the generated hypernetwork is more similar to the original one. Similarly, the Tensors method shows a decreasing trend in hyperedge deletion for all six hypernetworks, while the increasing trend is not significant in the hyperedge addition for Restaurant-Rev, Bars-Rev, NDC-classes, and Algebra. Moreover, the six centrality methods, namely, ECC, EDC, HCC, HDC, NDC, and VC, show either an indistinct increasing or a decreasing trend in hyperedge deletion for the six hypernetworks.

The method we proposed contains a parameter $\beta$ that emphasizes the importance of global and local dissimilarity between two hypernetworks. We further explore how the value of HD changes with $\beta$. The results are given in Figure 7 for six different hypernetworks. We observe that the values of HD with higher $\beta$ values are lower for hyperedge deletion process. However, for the hyperedge addition process, there is no consistent pattern of how HD changes with $\beta$.