A depth-first search approach to detect the community structure of weighted networks using the neighbourhood proximity measure

Community structure detection techniques play a prominent role in analysing complex networks, emerging from diverse domains. A major reason why this area is flourishing is that there is no uniformly acceptable definition of a “community”—rather it is an outcome of such algorithms which is often sought to be optimal with respect to certain quality metric(s). Since the quality metrics themselves are under immense scrutiny, the task of designing accurate community detection algorithms becomes even more challenging. Besides, there are very limited number of good algorithms that uncover community structures in weighted networks, whether overlapping or disjoint. Consequently, in this article we have attacked on the fundamental problem of disjoint community detection in weighted networks. Specifically, we have designed an algorithm called NP-DFS, which combines the concept of neighbourhood proximity (NP) with the fundamental graph traversal technique, depth-first search (DFS), to discover disjoint community structure in weighted complex networks. The time complexity of NP-DFS is \(\mathcal {O}(nk^3\log k)\) $\mathcal{O}(n{k}^{3}logk)$ , where n is the number of nodes and k is the maximum degree of the input network. NP-DFS has been well tested on artificial as well as on real-world networks, and has been empirically found to perform superior than many famed algorithms such as LOUVAIN and INFOMAP, and indeed gives tough competition to LEIDEN. The proposed algorithm is also much faster than many well established algorithms such as WALKTRAP, OSLOM and PYCOMBO.