Hypermodularity and community detection in hypergraphs
Charo I. del Genio · 2024
Read Hypermodularity and community detection in hypergraphs by Charo I. del Genio (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06935.txt.
Introduction
Charo I del Genio, writing alone, extends a classic community-finding tool to networks with group interactions. The 2024 paper concerns hypergraphs, where one link can join many nodes at once, as in team authorship or group chats. Standard community detection assumes pairwise links, so it misses structure that only groups create.
The author defines a hypermodularity score that judges how well a grouping fits the higher-order links. With that score in hand, spectral methods, which use matrix eigenvalues, can search for good groupings. Tests on synthetic networks and real data show the groupings reflect how the modeled interactions actually behave. The tool helps analysts extract hidden modules from data sets where relationships come in groups rather than pairs.
Catalog record
| CREATOR | Charo I. del Genio |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06935
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hypermodularity and community detection in hypergraphs Charo I. del Genio Abstract Numerous networked systems feature a structure of nontrivial communities, which often correspond to their functional modules. Such communities have been detected in real-world biological, social and technological systems, as well as in synthetic models thereof. While much effort has been devoted to developing methods for community detection in traditional networks, the study of community structure in networks with higher-order interactions is still not as extensively explored. In this article, we introduce a formalism for the hypermodularity of higher-order networks that allows us to use spectral methods to detect community structures in hypergraphs. We apply this approach to synthetic random networks as well as to real-world data, showing that it produces results that reflect the nature and the dynamics of the interactions modelled, thereby constituting a valuable tool for the extraction of hidden information from complex higher-order data sets. I Introduction Many complex systems have the structure of a network, in which pairs of elements of a discrete set, called the nodes, are connected when they share a common property [ 1 , 2 , 3 , 4 ] . Typically, such networks have structural features with different characteristic length scales. The smallest length scale is that of the number of links (also called edges) of a given node, which takes the name of degree. The links between the neighbours of a specific node define the local neighbourhood structure, which is the next larger length scale. As one considers the whole network, one may find sets of nodes whose elements have more connections amongst themselves than they have with nodes in other such sets. When this happens, these mesoscale sets take the name of communities, and the network is said to exhibit a nontrivial community structure. The presence of network communities has been detected in a large number of real-world systems, such as protein networks, social networks, food webs, and synthetic models of complex systems of diverse nature [ 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 ] . In general, the community structure of a network affects the behaviour of the system, and often one can trace a direct correspondence between communities and structural units responsible for specific functions. As a result, a large number of methods have been developed to detect communities in networks [ 14 , 15 ] . A particularly successful approach is the maximization of a quality function that measures how pronounced a partition of a network into communities is by computing the difference between the density of the observed intracommunity links and that of a suitably chosen null model. The most commonly used such function is called modularity [ 16 ] . However, finding the network partition that maximizes it is an NP-hard computational problem [ 17 ] . Thus, large efforts have been devoted to creating algorithms that provide the best possible approximation to the global maximum in a workable running time [ 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 ] . Recently, however, it has become increasingly clear that dyadic interactions are only a part of the important relationships that occur in complex systems. In fact, researchers have recognized the relevance of collective interactions for the functioning of systems as diverse as social groups, neural networks and multispecies assemblages of microorganisms, sparking a new interest in structures with higher-order interactions [ 28 , 29 ] . As a result, the main type of structural backbone that is currently generating considerable attention is no longer that of a graph, but rather that of a hypergraph. In hypergraphs, edges do not necessarily connect pairs of elements, but rather they can connect triplets, quadruplets, or any other number of nodes [ 30 ] . Unfortunately, the landscape of research on the subject of community detection in hypergraphs is not as well developed as in the case of traditional graphs. However, several methods have been proposed in recent years that address the problem from different directions. In some instances, these approaches are dynamical in nature, and analyze the outcome of a stochastic process on the hypergraph to infer its structure of modules and communitites [ 31 ] . Other methods, instead, rely on projecting the hypergraph onto a graph [ 32 ] , or on creating an auxiliary graph on which to carry out a community-detection procedure [ 33 ] . At the cost of a significant potential to lose information, especially when performing projections [ 29 ] , these techniques have the advantage of reducing the dimensionality of the problem, and resulting, therefore, in faster algorithms. A similar idea of dimensional reduction is behind methods based on embedding, in which the starting hypergraph is related to a lower-dimensional Euclidean space, and communities are detected by solving an optimization problem or via the application of existing clustering algorithms [ 34 , 35 ] . Such embeddings can themselves be obtained via the application of spectral methods, which have already proved extremely powerful for the task of finding communities in classic networks [ 16 ] . Indeed, spectral approaches often form the basis of the more advanced higher-order methods, where they are occasionally integrated by Bayesian inference algorithms [ 36 ] . The already mentioned possibility of information loss has also led to the development of algorithms that operate directly on the whole hypergraph. In this case, tensor methods are necessary, as one needs to relate the existence of communities to some property of the adjacency tensor of the higher-order network. One possible approach is to use the idea of tensor decomposition, which has been, in fact, long suggested as being applicable to community detection [ 37 ] , and has been eventually used for this goal, once more in conjunction with a Bayesian framework [ 38 ] . Alternatively, others have exploited the spectral features of higher-order equivalents of the graph Laplacian, effectively extending to higher-order structures the existing knowledge of the relation between the Laplacians of traditional graphs and the presence of communities [ 39 ] . An exception to these approaches is an extension to hypergraphs of the Chung-Lu model, which results in a modularity measure that is closely related to the one originally used in traditional networks [ 40 , 41 ] . Here, we introduce and characterize modularity for hypergraphs using a formalism that allows us to create a spectral algorithm for its maximization. Our method differs from the existing ones mentioned above as it does not rely on embeddings of any kind and does not require the structure of the higher-order network to be a simplicial complex. Also, while the core of our approach is a spectral method, this is applied onto a modularity tensor, rather than on the adjacency tensor or the Hodge Laplacian of the structure. Note that the specific form of the modularity measure we use is mathematically equivalent to that of Refs. [ 40 ] and [ 41 ] . However, we are able to operate a tensor decomposition on it because of the different formalism adopted, which rests on a derivation of a