Random Hypergraph Model
Preserving Two-mode Clustering Coeﬃcient
Rikuya Miyashita, Kazuki Nakajima, Mei Fukuda, and Kazuyuki Shudo
Tokyo Institute of Technology

Abstract. Real-world complex systems often involve interactions among
more than two nodes, and such complex systems can be represented byhypergraphs. Comparison between a given hypergraph and randomized
hypergraphs that preserve speciﬁc properties reveal eﬀects or dependencies of the properties on the structure and dynamics. In this study, we
extend an existing family of reference models for hypergraphs to generaterandomized hypergraphs that preserve the pairwise joint degree distribution and the degree-dependent two-mode clustering coeﬃcient of theoriginal hypergraph. Using empirical hypergraph data sets, we numerically show that the extended model preserves the properties of the nodeand hyperedge as designed.
Keywords: Hypergraph · Two-mode clustering coeﬃcient · Conﬁguration model

1

Introduction

Networks are often used to represent complex systems that consist of nodes andpairwise interactions (i.e., edges) among the nodes [4]. On the other hand, realworld complex systems often involve interactions among more than two nodes[2]. For example, in email networks, there are multiple senders and receivers ofa single e-mail [7]; in co-authorship networks, there are more than two coauthors for a single paper [11, 15]. Such complex systems can be represented as
hypergraphs consisting of a set of nodes and hyperedges, where each hyperedge
contains an arbitrary number of nodes.
Randomized networks that preserve speciﬁed properties are often used foranalyzing the structure and dynamics of empirical networks [12, 8, 14]. In general, by comparing the structure or dynamics between a given network andrandomized networks that preserve speciﬁed properties of the original network,
we investigate how the preserved properties aﬀect the structure or dynamics ofinterest of the original network [5]. The dK-series [6, 8, 14] is a family of models
to generate such randomized networks. Given a network, the dK-series generates
randomized networks that preserve up to the degree of each node, the pairwise
joint degree distribution, and the degree-dependent clustering coeﬃcient. A recent study proposed the hyper dK-series, which is an extension of the dK-series
to the case of hypergraphs [10]. The hyper dK-series preserves up to the degree
distribution of the node, the pairwise joint degree distribution of the node, theProc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

2

R. Miyashita et al.

degree-dependent redundancy coeﬃcient of the node, and the size distributionof the hyperedge in the original hypergraph.
In this study, we extend the hyper dK-series to preserve the pairwise joint
degree distribution of the node and the degree-dependent two-mode clustering
coeﬃcient of the node, proposed in Ref. [13]. Using empirical hypergraph data
sets, we numerically show that the extended hyper dK-series preserves the properties of a given hypergraph as designed. This paper is an extended version of
our previous work published as an extended abstract [9]. This paper presents
deﬁnitions and notations in Section 2 and further analysis and consideration of
the experimental results in Section 4 and Fig. 1.

2

Preliminaries

We represent an unweighted hypergraph that consists of a set of nodes V ={v1 , . . . , vN } and a set of hyperedges E = {e1 , . . . , eM }, where N is the numberof nodes and M is the number of hyperedges. Then, we denote by G = (V, E, E)
the bipartite graph that corresponds to the given hypergraph, where E is a setof edges in the bipartite graph. An edge (vi , ej ) is connected to each node vi andeach hyperedge ej if and only if vi belongs to the hyperedge ej in the hypergraph.
We assume that G does not contain multiple edges.
We denote by ki and sj the degree of node vi (i.e., the number of hyperedges
to which vi belongs) and the size of hyperedge ej (the number of nodes thatbelong to the hyperedge ej ), respectively. We also denote by k̄ and s̄ the average
degree of the node and the average size of the hyperedge, respectively.
We use the joint degree distribution and the average degree of the nearest
neighbors of nodes with degree k, which were deﬁned in Ref. [10]. We denote by
P (k, k ′ ) the joint degree distribution of the node [10]. We denote by knn (k) by
the average degree of the nearest neighbors of nodes with degree k [10].
We deﬁne the two-mode clustering coeﬃcient of each node vi [13]:ci =(number of closed 4-paths centered on node vi ).
(number 4-paths centered on node vi )We denote by c̄ the average two-mode clustering coeﬃcient of the node. We
deﬁne c(k) the degree-dependent two-mode clustering coeﬃcient of the node as
1c(k) =
N (k)

N
∑

ci ,

i=1,ki =kwhere N (k) is the number of nodes with degree k.

3Extending the hyper dK-series to the case of dv = 2.5+

The hyper dK-series generates a bipartite graph that preserves the joint degree
distributions of the node in the subgraphs of size dv ∈ {0, 1, 2, 2.5} or less andProc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

Random Hypergraph Model Preserving Two-mode Clustering Coeﬃcient

3

Table 1. Data sets. N : number of nodes, M : number of hyperedges, M: number ofedges in the corresponding bipartite graph, k̄: average degree of the node, s̄: average
size of the hyperedge, c̄: average two-mode clustering coeﬃcient of the node, ¯
l: average
shortest path length between nodes.
Data
email-Enron
NDC-classes
primary-school

N
143
628
242

M
M
k̄
1,512 4,550 31.82
816
5,688
9.06
12,704 30,729 126.98

s̄
3.01
6.97
2.42

c̄
0.68
0.31
0.70

¯
l
2.08
3.53
1.73

Refs.
[7, 3][3][16, 3]the size distributions of the hyperedge in the subgraphs of size de ∈ {0, 1} or lessin the given bipartite graph [10]. We extend the model to the case of dv = 2.5+
and de ∈ {0, 1} to generate a randomized bipartite graph that preserves the joint
degree distribution and the degree-dependent two-mode clustering coeﬃcient of
the node in addition to the average or distribution of the hyperedge’s size.
In the model with dv = 2.5+ and de ∈ {0, 1}, we ﬁrst generate a randomized
bipartite graph with de = 2 and given de using the original hyper dK-series.
Then, we repeat the rewiring process for the generated bipartite graph [10]. We
select a pair of edges, (vi , ej ) and (vi′ , ej ′ ), in the bipartite graph such that i ̸= i′ ,j ̸= j ′ , and ki = ki′ uniformly at random. We replace (vi , ej ) and (vi′ , ej ′ ) by
(vi , ej ′ ) and (vi′ , ej ) if and only if the normalized L1 distance deﬁned as∑M|c′ (k) − c(k)|D2.5+ = k=1∑M
k=1 c(k)decreases, where c′ (k) represents the degree-dependent two-mode clustering coeﬃcient of the node for the hypergraph after rewiring the edge-pair. The rewiring
procedure preserves the pairwise joint degree distribution of the node and thesize of each hyperedge. We repeat the rewiring attempts R = 500M times.

4

Experiments

We apply the extended hyper dK-series to three empirical hypergraphs. The
email-Enron hypergraph is an email network [7, 3], where nodes are email addresses and hyperedges are sets of all addressees of senders and receivers ofeach email. The NDC-classes hypergraph is a drug network [3], where nodes areclass labels and hyperedges are sets of class labels applied to each drug. The
primary-school hypergraph is a contact network [16, 3], where nodes are people
and hyperedges are sets of people who contact each other face-to-face. Table 1
shows the properties of the largest connected component for the data sets.
Table 2 shows the distance in ﬁve properties between the original hypergraphand the hypergraphs generated by the hyper dK-series with dv ∈ {0, 1, 2, 2.5, 2.5+}
and de ∈ {0, 1}. We calculated the Kolmogorov-Smirnov distance between the
cumulative distributions of the degree distribution of the node for the original hypergraph and the generated hypergraphs. For the other properties, we calculated

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

4

R. Miyashita et al.

Table 2. Distance between the empirical hypergraphs and those generated by thereference models.
Data
email-Enron(dv , de )(0, 0)(1, 0)(2, 0)(2.5, 0)(2.5+, 0)(0, 1)(1, 1)(2, 1)(2.5, 1)(2.5+, 1)
NDC-classes(0, 0)(1, 0)(2, 0)(2.5, 0)(2.5+, 0)(0, 1)(1, 1)(2, 1)(2.5, 1)(2.5+, 1)
primary-school (0, 0)(1, 0)(2, 0)(2.5, 0)(2.5+, 0)(0, 1)(1, 1)(2, 1)(2.5, 1)(2.5+, 1)

P (k)
0.434
0.000
0.000
0.000
0.000
0.406
0.000
0.000
0.000
0.000
0.614
0.000
0.000
0.000
0.000
0.597
0.000
0.000
0.000
0.000
0.380
0.000
0.000
0.000
0.000
0.368
0.000
0.000
0.000
0.000

knn (k)
0.420
0.202
0.012
0.013
0.013
0.412
0.200
0.035
0.027
0.032
0.741
0.388
0.046
0.045
0.043
0.751
0.389
0.022
0.019
0.021
0.429
0.089
0.006
0.005
0.007
0.451
0.089
0.014
0.015
0.014

c(k)
0.781
0.206
0.207
0.222
0.023
0.772
0.197
0.191
0.198
0.026
0.962
0.368
0.208
0.201
0.035
0.951
0.328
0.158
0.156
0.023
0.848
0.121
0.111
0.109
0.008
0.868
0.126
0.166
0.180
0.010

P (s)
0.158
0.160
0.160
0.160
0.160
0.000
0.000
0.000
0.000
0.000
0.252
0.248
0.248
0.248
0.248
0.000
0.000
0.000
0.000
0.000
0.303
0.307
0.307
0.307
0.307
0.000
0.000
0.000
0.000
0.000

P (l)
0.595
0.491
0.429
0.416
0.368
0.647
0.491
0.452
0.427
0.414
1.585
1.322
0.799
0.712
0.467
1.612
1.417
0.749
0.722
0.609
0.856
0.707
0.374
0.371
0.313
0.535
0.434
0.246
0.218
0.276

the normalized L1 distance between the properties for the original hypergraphand the generated hypergraphs.
We make the following observations for the three empirical hypergraphs.
First, the distances for P (k) is equal to 0 for dv = 2.5+ and de ∈ {0, 1}, as expected. Second, the distances for knn (k) are quite small values in the models withdv ∈ {2.5, 2.5+} and de ∈ {0, 1}, which indicates that the models approximately
preserve knn (k). Third, the distance for c(k) is much smaller in the model with
dv = 2.5+ than that in the model with dv = 2.5 for any de ∈ {0, 1}. Fourth,
the model with (dv , de ) = (2.5+, 0) and de = 0 has a somewhat distance for
P (s) but that with (dv , de ) = (2.5+, 1) has no distance for P (s), as expected.
Finally, the model with dv = 2.5+ often preserves more accurately P (l) thanthat with dv = 2.5 for any de = {0, 1}, whereas the distance is still not small in

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

Empirical
dv = 0dv = 1
dv = 2
dv = 2.5
dv = 2.5+101

100knn(k)

80
70
60
50
40
30
20
10
0

102

Degree k

100

0.8

0.6

0.6

0.4
0.2
101

100

102

101

102

Degree k

0.4

0.0

102

Degree k

0.7

Empirical
dv = 0dv = 1
dv = 2
dv = 2.5
dv = 2.5+

0.6
0.5
0.4
0.3
0.2
0.1
0.0

101

5

0.2
100

Degree k

0.7
0.6

Probability

0.0

Probability

80
70
60
50
40
30
20
10
0

0.8

c(k)

c(k)

knn(k)

Random Hypergraph Model Preserving Two-mode Clustering Coeﬃcient

0.5
0.4
0.3
0.2
0.1

1

2

3

Shortest path length

4

0.0

1

2

3

Shortest path length

4

Fig. 1. Structural properties of the email-Enron hypergraph and the hypergraphs generated by the reference models. The ﬁgures in the left column show the results forde = 0. The ﬁgures in the right column show the results for de = 1.

both models. Figure 1 shows knn (k), c(k), and P (l) for the original email-Enron
hypergraph and hypergraphs generated by the hyper dK-series.

5

Conclusion

We extended the hyper dK-series to generate a randomized hypergraph that
preserves the pairwise joint degree distribution and the two-mode clustering
coeﬃcient. We applied the extended hyper dK-series to three empirical hypergraphs. We numerically showed that the model with dv = 2.5+ preserves exactly
the degree distribution of the node, approximately the pairwise joint degree distribution of the node, and approximately the degree-dependent two-mode clustering coeﬃcient. We also found that the model with dv = 2.5+ often preserves
more accurately the distribution of the shortest-path length than the existingmodel with dv = 2.5. Future work includes the application of the extended hyper
dK-series to simulations of dynamical processes in hypergraphs [1].

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

6

R. Miyashita et al.

References
1. Battiston, F., Amico, E., Barrat, A., Bianconi, G., Ferraz de Arruda, G.,
Franceschiello, B., Iacopini, I., Kéﬁ, S., Latora, V., Moreno, Y., Murray, M.M.,
Peixoto, T.P., Vaccarino, F., Petri, G.: The physics of higher-order interactions incomplex systems. Nature Physics 17, 1093–1098 (2021)
2. Battiston, F., Cencetti, G., Iacopini, I., Latora, V., Lucas, M., Patania, A., Young,J.G., Petri, G.: Networks beyond pairwise interactions: Structure and dynamics.
Physics Reports 874, 1–92 (2020)
3. Benson, A.R., Abebe, R., Schaub, M.T., Jadbabaie, A., Kleinberg, J.: Simplicial
closure and higher-order link prediction. Proceedings of the National Academy of
Sciences 115, E11221–E11230 (2018)
4. Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.U.: Complex networks: Structure and dynamics. Physics Reports 424, 175–308 (2006)
5. Cimini, G., Squartini, T., Saracco, F., Garlaschelli, D., Gabrielli, A., Caldarelli, G.:
The statistical physics of real-world networks. Nature Reviews Physics 1, 58–71(2019)
6. Gjoka, M., Kurant, M., Markopoulou, A.: 2.5K-graphs: From sampling to generation. In: 2013 Proceedings IEEE INFOCOM. pp. 1968–1976 (2013)
7. Klimt, B., Yang, Y.: The Enron corpus: A new dataset for email classiﬁcation
research. In: Proceedings of the 15th European Conference on Machine Learning.
pp. 217–226 (2004)
8. Mahadevan, P., Krioukov, D., Fall, K., Vahdat, A.: Systematic topology analysis
and generation using degree correlations. In: Proceedings of the 2006 Conference
on Applications, Technologies, Architectures, and Protocols for Computer Communications. pp. 135—-146 (2006)
9. Miyashita, R., Nakajima, K., Fukuda, M., Shudo, K.: Randomizing hypergraphspreserving two-mode clustering coeﬃcient. In: 2023 IEEE International Conference
on Big Data and Smart Computing (BigComp). pp. 316–317 (2023)
10. Nakajima, K., Shudo, K., Masuda, N.: Randomizing hypergraphs preserving degree correlation and local clustering. IEEE Transactions on Network Science andEngineering 9, 1139–1153 (2022)
11. Newman, M.E.J.: The structure of scientiﬁc collaboration networks. Proceedingsof the National Academy of Sciences 98, 404–409 (2001)
12. Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Random graphs with arbitrary degree distributions and their applications. Physical Review E 64, 026118 (2001)
13. Opsahl, T.: Triadic closure in two-mode networks: Redeﬁning the global and local
clustering coeﬃcients. Social Networks 35, 159–167 (2013)
14. Orsini, C., Dankulov, M.M., Colomer-de Simón, P., Jamakovic, A., Mahadevan, P.,
Vahdat, A., Bassler, K.E., Toroczkai, Z., Boguñá, M., Caldarelli, G., Fortunato, S.,
Krioukov, D.: Quantifying randomness in real networks. Nature Communications
6, 8627 (2015)15. Patania, A., Petri, G., Vaccarino, F.: The shape of collaborations. EPJ Data Science 6, 18 (2017)16. Stehlé, J., Voirin, N., Barrat, A., Cattuto, C., Isella, L., Pinton, J.F., Quaggiotto,
M., Van den Broeck, W., Régis, C., Lina, B., Vanhems, P.: High-resolution measurements of face-to-face contact patterns in a primary school. PLOS ONE 6,e23176 (2011)

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023