Algorithms Based On The Generalized Modularity Density For Community Detection

Recently, the complex network as a powerful tool for describing andanalyzing the complex systems in real world has been extensively studied. Thecomplexity of complex network makes it desirable to find natural partition intosubstructure that can not only act as simplified descriptions but also provideinsight into the structure and function of the overall system. Community structureas a local description of the whole network has a considerable merit of practice incomputer science, bioinformatics and sociology etc.In community detection, how to quantity the partitioning of the networkinvolved and how design efficient and effective algorithm to extract thecommunity structure hidden in complex networks are two key steps. To deal withthe first challenge, Newmann et al. proposed the well known modularity bycomparing the topological structure in real networks and the random networkswith the same degree distribution. Albeit optimizing the modularity is an NP-hardproblem, most of the current algorithms employed this strategy. To overcome theresolution limit problem of modularity, Li et al. presented the modularity densityby taking into account the difference between the densities in-communities andout-communities. They also proved that the proposed measure can tolerate theresolution limit at large extent. It is, however, not enough since it cannot beapplied to the weighted networks. Such a fault is very fatal since most of the realnetworks are weighted. To handle this problem, we develop a generalizedmodularity density and design a novel algorithm to identify the communitystructure by optimizing the constructed measure. The experimental resultsdemonstrate that the proposed measure is better than the modularity density.To enhance the capability of the proposed measure, a novel communitydetection algorithm is constructed for discovering the protein complexes inprotein-protein interaction networks. A software is also developed. Theexperimental results show that the algorithm can detect the overlapping andnon-overlapping meaningful protein complexes efficiently.