Research On Algorithms For Finding Robust Community Structures

It has been shown that many real world networks have structures of modules orcommunities due to the fact that information technology is developing at staggeringrate, such as the biological system, sophisticated computer system, etc. The communitystructures detection in complex network is very crucial since they provide insight intothe substructures of the whole network. At present, many methods have been proposedfor efficiently detecting community structures in complex network, such as spectralclustering, betweenness-based method, fuzzy clustering approach, etc. At the sametime, some criteria were proposed to measure the quality of the given partition of anetwork, such as modularity function Q, modularity density D value, etc.So far, all community discovering algorithms are focusing on the partition of anetwork, neglecting the robustness of community structure. In some applications, weonly focus on the communities which have robustness feature, rather than a partition ofthe network.In this paper, two novel algorithms are proposed for finding significant structures-robust communities in complex network. The algorithm based on Bayesian network isdevised from the point of view that the interactions of robust community are closerthan average community. Through constructing Bayesian network for every commoncommunity, according to conditional probabilities table and prior probabilities forreasoning, the posterior probabilities of every node being in a robust community isobtained to extract robust communities. The other algorithm based on matrixperturbation theory is devised from the stability of robust community to smallperturbations in network structure. Robust communities have been extracted throughmatching the community structures of original network and disturbed network. Finally,we experimentally verify the effectiveness of two algorithms in social networks andartificial networks.