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. 1

Fig. 2

40517_2023_263_Article_IEq2.gif

Fig. 1

Fig. 11

Fig. 4

Fig. 3

Fig. 4

Fig. 8

Fig. 3

Fig. 4

Fig. 12

Fig. 1

Fig. 3

Fig. 2

Fig. 11

Fig. 3

Fig. 1

Fig. 1

12938_2023_1137_Article_IEq68.gif

Fig. 2

40517_2023_267_Article_IEq8.gif

Fig. 10

Fig. 1

Fig. 1

Fig. 1

Fig. 1

Fig. 7

Fig. 4

Fig. 3

Fig. 7

Fig. 3

Fig. 5

40798_2023_622_Article_IEq7.gif

40798_2023_622_Article_IEq6.gif

40798_2023_622_Article_IEq4.gif

Fig. 5

Fig. 9

40798_2023_622_Article_IEq1.gif

41512_2023_153_Article_IEq116.gif

Fig. 2

Fig. 1

Fig. 3

Fig. 3

Fig. 4

Fig. 1

12938_2023_1137_Article_IEq32.gif

40517_2023_267_Article_IEq6.gif

40517_2023_267_Article_IEq5.gif

40517_2023_267_Article_IEq4.gif

40517_2023_267_Article_IEq3.gif

Fig. 2

Fig. 2

Fig. 3

Fig. 5

Fig. 8

Fig. 1

Fig. 1

Fig. 7

Fig. 3

Fig. 1

Fig. 3

41512_2023_153_Article_IEq102.gif

41512_2023_153_Article_IEq101.gif

Fig. 2

Fig. 1

Fig. 1

Fig. 2

Fig. 4

41512_2023_153_Article_IEq93.gif

Fig. 6

41512_2023_153_Article_IEq73.gif

Fig. 2

Fig. 4

Fig. 1

Fig. 4

13570_2023_282_Article_IEq21.gif

13570_2023_282_Article_IEq20.gif

13570_2023_282_Article_IEq19.gif

13570_2023_282_Article_IEq18.gif

13570_2023_282_Article_IEq17.gif

13570_2023_282_Article_IEq16.gif

13570_2023_282_Article_IEq15.gif

Fig. 1

13570_2023_282_Article_IEq13.gif

13570_2023_282_Article_IEq12.gif

13570_2023_282_Article_IEq11.gif

Fig. 3

13570_2023_282_Article_IEq9.gif

13570_2023_282_Article_IEq8.gif

13570_2023_282_Article_IEq7.gif

13570_2023_282_Article_IEq6.gif

13570_2023_282_Article_IEq5.gif

13570_2023_282_Article_IEq4.gif

13570_2023_282_Article_IEq2.gif

13570_2023_282_Article_IEq1.gif

13690_2023_1151_Article_IEq13.gif

40798_2023_599_Article_IEq34.gif

13690_2023_1151_Article_IEq7.gif

40798_2023_599_Article_IEq23.gif

40798_2023_599_Article_IEq20.gif

Fig. 2

13690_2023_1151_Article_IEq3.gif

Fig. 2

Fig. 4

40517_2023_266_Article_IEq55.gif

40517_2023_266_Article_IEq37.gif

Fig. 6

Fig. 5

Fig. 1