Detecting and generating overlapping nested communities

Applied Network Science

Research

Imre Gera¹  András London² 

[1] Department of Computational Optimization, University of Szeged, Árpád tér 2, 6720, Szeged, Hungary;Department of Computational Optimization, University of Szeged, Árpád tér 2, 6720, Szeged, Hungary;Department of Operations Research and Mathematical Economics, Poznań University of Economics and Business, 61-875, Poznań, Poland;

关键词: Nestedness;    Community detection;    Network science;   

DOI  :  10.1007/s41109-023-00575-2

 received in 2023-04-28, accepted in 2023-07-18,  发布年份 2023

来源: Springer

【 摘 要 】

Nestedness has been observed in a variety of networks but has been primarily viewed in the context of bipartite networks. Numerous metrics quantify nestedness and some clustering methods identify fully nested parts of graphs, but all with similar limitations. Clustering approaches also fail to uncover the overlap between fully nested subgraphs, as they assign vertices to a single group only. In this paper, we look at the nestedness of a network through an auxiliary graph, in which a directed edge represents a nested relationship between the two corresponding vertices of the network. We present an algorithm that recovers this so-called community graph, and finds the overlapping fully nested subgraphs of a network. We also introduce an algorithm for generating graphs with such nested structure, given by a community graph. This algorithm can be used to test a nested community detection algorithm of this kind, and potentially to evaluate different metrics of nestedness as well. Finally, we evaluate our nested community detection algorithm on a large variety of networks, including bipartite and non-bipartite ones, too. We derive a new metric from the community graph to quantify the nestedness of both bipartite and non-bipartite networks.

【 授权许可】

CC BY   
© Springer Nature Switzerland AG 2023

【 图 表 】

Fig. 2

Fig. 3

Fig. 7

Fig. 5

Fig. 2

Fig. 4

Fig. 5

Fig. 1

12862_2023_2133_Article_IEq80.gif

Fig. 6

Fig. 2

Fig. 1

Fig. 1

Fig. 2

Fig. 2

Fig. 1

Fig. 1

Fig. 1

Fig. 1

Fig. 3

12862_2023_2148_Article_IEq5.gif

Fig. 11

Fig. 4

Fig. 1

Fig. 1

Fig. 1

Fig. 1

12862_2023_2133_Article_IEq61.gif

Fig. 2

Fig. 5

Fig. 3

Fig. 2

Fig. 2

12862_2023_2133_Article_IEq56.gif

Fig. 6

Fig. 4

Fig. 4

Fig. 2

Fig. 1

Fig. 1

Fig. 1

Fig. 4

Fig. 1

Fig. 4

Fig. 2

Fig. 2

Fig. 2

Fig. 1

Fig. 5

Fig. 4

Fig. 1

Fig. 5

Fig. 3

Fig. 2

Fig. 4

Fig. 3

12862_2023_2133_Article_IEq10.gif

Fig. 1

Fig. 1

Fig. 1

Fig. 2

Fig. 1

Fig. 4

40708_2023_198_Article_IEq16.gif

Fig. 3

Fig. 3

Fig. 4

Fig. 3

Fig. 2

Fig. 4

Fig. 2

Fig. 2

Fig. 3

Fig. 1

Fig. 2

Fig. 2

Fig. 2

Fig. 6

Fig. 3

Fig. 1

12888_2023_5012_Article_IEq5.gif

12888_2023_5012_Article_IEq4.gif

Fig. 1

12888_2023_5012_Article_IEq2.gif

12888_2023_5113_Article_IEq7.gif

12888_2023_5113_Article_IEq6.gif

12888_2023_5113_Article_IEq5.gif

12888_2023_5113_Article_IEq3.gif

12888_2023_5113_Article_IEq2.gif

12888_2023_5113_Article_IEq1.gif

Fig. 4

40517_2023_261_Article_IEq40.gif

Fig. 1

40517_2023_261_Article_IEq36.gif

13690_2023_1154_Article_IEq13.gif

13690_2023_1154_Article_IEq5.gif

40517_2023_261_Article_IEq6.gif

40517_2023_261_Article_IEq5.gif

40517_2023_261_Article_IEq4.gif

40517_2023_261_Article_IEq3.gif

40517_2023_261_Article_IEq2.gif

Fig. 4

13690_2023_1154_Article_IEq2.gif

Fig. 1

42490_2023_74_Article_IEq62.gif

Fig. 2

13690_2023_1172_Article_IEq5.gif

13690_2023_1172_Article_IEq2.gif

42490_2023_74_Article_IEq37.gif

Fig. 2

42490_2023_74_Article_IEq3.gif

Fig. 5

Fig. 1

Fig. 3

Fig. 9

Fig. 11

Fig. 1