Detecting Communities in Networks and Performance Prediction Based on Relation Strength Measurement - Behera, Soom Satyam (Université d'Ottawa / University of Ottawa, 2016)
Complex networks is an interdisciplinary research area which focuses on the study of properties of complex systems that have many functional or structural subunits. Community detection algorithms are one of the major approaches to analyse complex networks with multilevel or overlapping community structures. This research work focuses on constructing a novel community detection approach for simplification of a given complex demographic network. The general process of the abstraction from concrete problems as well as the general definition of communities have not been well defined and all the existing methods are derived from specific backgrounds, leaving the reliabilities in other fields open to ques- tion. This specificity of the existing methods reveals the need for a general approach for community definition and detection. Here, we devise a general procedure to find community structures in concrete problems by classifying the concrete networks into two basic types: Transmission networks and Similarity networks. The relation among nodes in transmission networks are constructed by material transmission and the ones in similarity network are constructed by the similarity in properties of the nodes. We show that both the types can be represented based upon an unified graph model. Based on the model, we propose a generic approach, Relation Strength Measurement (RSM), to define the communities. We have demonstrated that the Effective Resistance Function (ERF), from the Klein and Randic’s electrical network model, is applicable for quantifying the relation among nodes. We have also introduced a community threshold parameter (CP) based on which, the RSM algorithm categorizes the network nodes into communities. We have compared the performance of our algorithm with other well known community detection methods. The simulation results show that the algorithm accurately obtains the division of community structure both in real-world and synthetic networks.
Keywords: Communities; Relation Strength Measurement; Community Threshold Parameter