Finding Community Structure via Rough K-Means in Social Network

Much of the data of scientific interest, particularly when independence of data is not assumed, can be represented in the form of networks where data nodes are joined together to form edges corresponding to some kind of associations or relationships. Such information networks abound, like protein interactions in biology, web page hyperlink connections in information retrieval on the Web, cellphone call graphs in telecommunication, co-authorships in bibliometrics, crime event connections in criminology, etc. All these networks, also known as social networks, share a common property, the formation of connected groups of information nodes, called community structures. These groups are densely connected nodes with sparse connections outside the group. Finding these communities is an important task for the discovery of underlying structures in social networks, and has attracted much attention in data mining research. In this paper, we present rough k-means method (RKM), a new community mining approach that, simply put, regards a community as a set of nodes, these communities have their lower and upper approximation sets. Our algorithm starts by selecting k nodes as the center nodes of communities in a given network then iteratively assembles node to their closest center node to form communities, and subsequently calculates new center node in each group around which to gather nodes again until convergence. Our intuitions are based on proven observations in social networks and the results are promising. Experimental results on benchmark networks verify the feasibility and effectiveness of our new community mining approach.