An Enhanced Discrete Artificial Bee Colony Algorithm for Community Detection in Social Networks

Abstract

Real world social network is represented as a graph structure which has a collection of non-empty set of nodes and set of connections of nodes. The nodes in a social graph are people, and edges represent the connection between them. People in the society are naturally grouped to form communities in their workplace, friendship and family. The study of complex social network topology has triggered the interest of many scientists in recent years. Some important features of a social network need to be understood in terms of node density in cluster, degree of node, reachability, size of network, geodesic distance and diameter. Thus, the idea of community within a social network has emerged as an educational tool for social network analysis that lays the foundation for some high-level initiatives. Finding community structure is the key to research the structural components of relationships in the social network. Community detection aims at grouping nodes based on the links between them to form strongly link sub groups of graph from the whole graph. Many community discovery techniques have been borrowed on inspired from the problem of hierarchical clustering, graph partitioning in modern graph theory, as well as the graph clustering or dense sub-graphs discovery problem in the graph mining area. These algorithms were designed to reveal the mesoscopic nature of various networks. It is not known how good the algorithm is in terms of computational time, efficiency of these algorithms and accuracy, which remains still open. Community detection in social network is one kind of the optimization problems because it cannot get exact solution and only get an optimal solution. So, various types of community detection algorithms attempt to capture the intuitive notation that nodes within the group have higher intra-density and have lower inter-density with other nodes in the other group. Population-based nature inspired optimization algorithms have attracted extensive research interests over the past decade. Researchers used these algorithms to search the hidden communities in social networks. An enhanced discrete artificial bee colony D-ABC algorithm is proposed for solving community detection problem in social networks. In this thesis,some of the challenges and applications of social network community discovery for analyzing network documents will be explored. The proposed system focuses on undirected and unweighted social networks and considers the connection of nodes for the community detection problem. The proposed algorithm D-ABC is designed with an effective initialization strategy with label-based solution representation and one way crossover operation of genetic operators is used in the search strategy process. D-ABC selects modularity function as the fitness function of each solution. The efficiency of searching process can be improved by heuristic function which contain genetic algorithm operations. Most of the real social network community detection problem do not know each community size and numbers of community. D-ABC algorithm can also detect communities in social network that does not know real community numbers and sizes. When it detects the communities on a network structure, it uses neighbor nodes similarity measurement. In this thesis, standard social datasets with ground-truth results and various scale real world networks without ground-truth from the Stanford Large Network Dataset Collection are used. The performance of the proposed system is assessed by accuracy, efficiency and effectiveness. The result indicates good quality with accurate communities as well as their density improvement.