Formalising and Detecting Community Structures in Real World Complex Networks

Community structure is an integral characteristic of real world networks whichever processes or areas they emerge from. This paper addresses the problem of community structure detection theoretically as well as computationally. The authors introduce a number of concepts such as the neighbourhood and strength of a subgraph, p-community, local maximal p-community, hubs, and outliers that play elemental role in formalising the concept of community structure in complex networks. A few preliminary results have been derived that lead to the development of an algorithm for community structure detection in undirected unweighted networks. The algorithm is based on a local seed expansion strategy that uses the concept of interaction coefficient. The authors have analysed the algorithm on a number of parameters such as accuracy, stability, and quality on synthetic and real world networks from different areas.