Research On Overlapping Community Detection Algorithm Based On Rough Sets

With the development of Internet and the progress of society,a large number of interrelated and interdependent data is produced in various fields every day,which forms different complex systems according to different themes.We abstract complex systems into complex networks.We treat the research object of complex system as a node in the complex network,and treat the relation between objects as an edge in the network.The understanding and analysis of complex networks can help us to mine different knowledge according to different topics,discover the hidden information,and deal with and predict problems.Mining community structure of complex network is an important research content,which has extremely irreplaceable role in recommendation system,information dissemination,behavior prediction and data mining.Overlapping nodes of community structure exist universally in life,and overlapping community detection algorithms make the divided community structure more effective.The complex network not only exists overlapping nodes,but also exists dynamic complexity,which nodes state of community structure changes constantly.In addition to topology information of networks,there is also rich node attribute information in real networks.At present,some community detection algorithms fail to describe overlapping area of community well,and do not consider nodes’ dynamics and attribute information.Considering overlapping nodes,dynamic characteristic of nodes and the rich attribute information of nodes in networks,the specific work of this thesis is as follows.1.An overlapping community detection method based on rough sets and density peaks was proposed in this paper.Firstly,the global similarities among network nodes are obtained by using grey correlation analysis method based on the traditional local similarity measure of network nodes.Then the global similarities among network nodes are converted to distance among nodes.The center nodes of the community are automatically selected by considering the network structure when applying density peaks based clustering method.Based on rough sets theory,the lower approximation,the upper approximation,and the boundary region of the community are defined according to the distance ratio relation among nodes in the network.The boundary region of the community is calculated repeatedly in each iteration until the optimal overlapping community structure is obtained.Experimental results show that the algorithm is effective and feasible.2.Considering overlapping nodes and dynamics of network community structure,an overlapping community detection method based on rough sets and distance dynamics model was proposed in this paper.First of all,according to the topology of the network,the algorithm selects K center nodes by combining node degree centrality and distance.And then combined with rough sets theory and distance dynamic model,distances between boundary region nodes and the lower approximation set nodes are changed iteratively.The boundary region nodes are reduced until the optimal overlapping community structure is found.Finally,we handle "pseudo" overlapping nodes according to two rules defined in this paper.Experimental results show that the improved algorithm is feasible and effective.3.In addition to topology information of networks,there is also rich node attribute information in real networks.Considering overlapping nodes and node attribute information,an overlapping community detection method based on rough sets which combines network structure and attribute information was proposed.First of all,the global similarities among network nodes combined topology information and node attribute information are obtained based on the traditional local structure similarity measure and local attribute similarity measure of network nodes.The global similarities among network nodes are converted to distances among nodes.Then we select K center nodes by combining node aggregation coefficient and global distances of nodes.Finally,overlapping community structure is divided based on rough sets theory.Experimental results show that the algorithm is effective and feasible.