Community Detection using Fortunato’s Performance Measure

Srushti Thakar, Amit A. Nanavati · 2025

Read Community Detection using Fortunato’s Performance Measure by Srushti Thakar, Amit A. Nanavati (2025) 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-2509-00938.txt.

Introduction

Srushti Thakar and Amit A Nanavati explore Fortunato's performance measure for finding communities in networks. The measure counts correctly interpreted pairs of vertices. A pair counts if both vertices share a group and an edge. It also counts if they sit in different groups with no edge. The setting is unweighted, undirected networks.

They give a greedy algorithm, fpGreed, that optimizes the measure at two levels. At vertex level, a vertex joins a group only if the value improves. At group level, two groups merge only on improvement. The algorithm alternates levels until no changes remain. A faster heuristic, fastFp, suits large datasets better. On datasets like YouTube and LiveJournal, fastFp performs well in time and quality.

Catalog record

CREATORSrushti Thakar, Amit A. Nanavati
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-00938

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Community Detection using Fortunato’s Performance Measure Srushti Thakar, Amit A. Nanavati Abstract In his paper on Community Detection [ Fortunato(2010) ] , Fortunato introduced a quality function called performance to assess the goodness of a graph partition. This measure counts the number of correctly “interpreted” pairs of vertices, i. e. two vertices belonging to the same community and connected by an edge, or two vertices belonging to different communities and not connected by an edge. In this paper, we explore Fortunato’s performance measure ( fp measure) for detecting communities in unweighted, undirected networks. First, we give a greedy algorithm fpGreed that tries to optimise the fp measure by working iteratively at two-levels, vertex-level and community-level. At the vertex level, a vertex joins a community only if the fp value improves. Once this is done, an initial set of communities are obtained. At the next stage, two communities merge only if the fp measure improves. Once there are no further improvements to be made, the algorithm switches back to the vertex level and so on. fpGreed terminates when there are no changes to any community. We then present a faster heuristic algorithm fastFp more suitable for running on large datasets. We present the quality of the communities and the time it takes to compute them on several well-known datasets. For some of the large datasets, such as youtube and livejournal , we find that Algorithm fastFP performs really well, both in terms of the time and the quality of the solution obtained. K eywords Social Network Analysis \cdot Community Detection \cdot Modularity 1 Introduction Community detection in networks has always been an important problem, with applications ranging from social and communication networks to biological systems. In their recent paper, “20 years of network community detection", the authors state that the fundamental technical challenge in the analysis of network data is the automated discovery of communities [ Fortunato and Newman(2022) ] . A generally accepted principle is that links within communities should be relatively frequent, while those between communities should be relatively rare [ Traag et al.(2011) ] . In order to distinguish between “good” and “bad” partitions of a network into communities, it would be useful to have a quantitative criterion to assess the goodness of a graph partition. A quality function is a function that assigns a number to each partition of a graph [ Fortunato(2010) ] . Modularity [ Newman and Girvan(2004) ] is one such quality function. It is based on the idea that a random graph is not expected to have a cluster structure, and therefore requires a suitable null model for its calculation. Apart from being a quality function, modularity optimization is itself a popular method for community detection and has been studied extensively [ Clauset et al.(2004) , Blondel et al.(2008) , Traag et al.(2019) , Fortunato and Barthelemy(2007) ] . The same paper [ Fortunato(2010) ] introduced another quality function performance (henceforth, fp , for “Fortunato’s performance"), that counts the number of correctly “interpreted” pairs of vertices, i. e. two vertices belonging to the same community and connected by an edge, or two vertices belonging to different communities and not connected by an edge. For a partition {\mathcal{P}} , the fp measure is calculated as: {\textit{f}p}({\mathcal{P}})={|\{(i,j)\in E,C_{i}=C_{j}\}|+|\{(i,j)\not\in E,C_{i}\not=C_{j}\}|\over{n(n-1)/2}} (1) 0\leq{\textit{f}p}({\mathcal{P}})\leq 1. This is a well-known quality measure and has been implemented in libraries such as Networkx [ Hagberg et al.(2008) ] for measuring the “goodness" of a network partition. The fp measure explicitly captures the intuitive notion that the more the number of intra-community edges, and the less the number of inter-community edges, the better. It does not account for null models based on random-graphs. While modularity (also a quality measure) has been explored extensively for community detection, to the best of our knowledge and somewhat surprisingly, fp has not. In this paper, we explore the fp measure as an optimisation metric for community detection in networks. Since modularity is a very popular metric, it has been studied extensively, and some of its limitations are now well-understood. Modularity contains an intrinsic scale that depends on the total number of links in the network [ Fortunato and Barthelemy(2007) ] . Modules that are smaller than this scale (resolution limit) may not be resolved, even in the extreme case where they are complete graphs connected by single bridges. The fp measure is simple, intuitive, and does not suffer from resolution-limit issues. Our Contribution. We discuss the suitability of the fp measure as a quality metric and highlight the advantages of using it in community detection. We present two algorithms: Algorithm fpGreed that greedily merges nodes into communities to maximise the fp measure. Algorithm fastFP employs a faster heuristic, suitable for running on large networks. We experimented with these two algorithms on various real-life datasets to find the fp values and the time it took to obtain them. In Section 2 , we discuss related work. Section 3 details Algorithm fpGreed which greedily optimises the fp measure at the vertex-level and the community-level. We show the results obtained from running Algorithm fpGreed on a few well-known networks. Section 4 discusses Algorithm fastFp , a faster heuristic, especially suitable for large networks. Section 5 tabulates the comparison of running both the algorithms on various datasets. Section 6 discusses the limitations of this paper and potential future work. 2 Why optimise fp ? (a) (b) Figure 1: Two examples from [ Fortunato and Barthelemy(2007) ] to show that modularity optimisation can lead to counter-intuitive results. In both the figures, modularity optimization leads to a partition where the cliques are combined into groups of two or more (represented by dotted lines). The intuitive and correct answer in each case is for each clique to be a separate community. Optimising the fp measure gives the intuitive answer (Table 1 ). Table 1: Resolution Limit Cases (a) and (b) with m=20, p=5 [ Fortunato and Barthelemy(2007) ] . Unlike Modularity optimisation, fp optimisation yields the expected number of modules(communities). modularity optimization fp optimization fp mod #modules fp mod #modules (a) 0.9706 0.8871 16 0.9973 0.8758 30 (b) 0.9780 0.5426 3 0.9967 0.5416 4 Modularity. Most community detection algorithms focus on the modularity optimization provided by Newman and Girvan [ Newman and Girvan(2004) ] . Modularity is a popular quality function that compares the actual observed intra-edge density with that expected under a random null model and is defined as: Q=\frac{1}{2m}\sum_{i,j}\left(A_{ij}-\gamma\frac{k_{i}k_{j}}{2m}\right)\delta(c_{i},c_{j}) The term k_{i}k_{j}\over 2m is the expected number of edges between nodes i and j in a random network given their degrees. However, modularity optimization for community detection suffers from resolution limitations, explaining its inability to identify small communities irrespective of their structural significance in the network. This limitation was analysed by Fortunato and Barthélemy [ Fortunato and Barthelemy(2007) ] , who demonstrated that modularity tends to merge smaller but meaningful communities. The authors present two examples (Figure 1 ), to explain this limitation. Table 1 presents the results of modularity optimisation and fp measure optimisation. The latter is able to correctly identify the number of communities. Potts Model Variants. To overcome the resolution-limit problem, the authors of [ Kumpula et al.(2007) ] identify a tunable parameter \gamma . By adjusting \gamma

Read the complete text