Application Of Rough Set And Ant Colony Algorithm On Community Discovery

Real-world networks are almost everywhere nowadays, lots of puzzles in daily life can be solved by the understanding of the structure of real-world network. People are more interested in the structure of social network in contrast to any other network structure; therefore a lot of work has been done in this field. The study of social network structure is meant to discover community structure. Generally, the community is a subset of tightly-linked vertices. Its connections among community vertices are relatively denser than the ones crossing to the rest of the network.By our study, we can understand and explain the complex community phenomena; moreover, we can handle the specific issues in our design when we have to build some network structure.In this thesis, we introduced some basic conceptions of the complex network and many famous algorithms for detecting community, and we analysis the advantages and disadvantages of every algorithm. Then we proposed two means based on soft computing to discover the community structure. Finally we tested our algorithm with two classic models of network dataset named Zachary Karate Club and College Football. Our algorithm proved to be not only effective but also with high accuracy.Two algorithms proposed in this paper are as follows:"Community Structure Detection Algorithm Based on Rough Set"is the first one. In this algorithm, we use information centrality as a measure of correlation between nodes. While dealing with the boundary nodes between communities we use upper and lower approximations subsets so as to better simulate the real world ,then we cluster nodes to certain community and identify the network to k communities , then identify the ideally community structure according to modularity, besides the k value needs not to be prior given. The algorithm is tested on two network dataset named Zachary Karate Club and College Football. "Community Structure Detection Algorithm Based on Ant Colony Algorithms"is the second. In this algorithm , we simulated the foraging behavior of ants, with the principle that the network path between nodes which are closely associated are sure to have more pheromone, in use of this feature we can select the core community in a social network, and then we deal with the boundary nodes, after all we have selected the whole community structure. By experiments, we discussed the setting of the number of ants and constant sensor threshold, which will surely do some impact on the convergence and accuracy of the algorithm.