Linkage Based Community Detection in Social Networks

Abstract

Community detection is one of important research problems in the field of social network analysis. It is the process of unfolding dense subgroups in the network also called as communities. Communities are the set of users which are strongly correlated with each other as compared to users lying outside of the subgroups. They correspond to the potential functional units in the complex network. Understanding the structural topology of the communities are quite useful in exploring the behaviour of the network. However, due to unprecedented growth of size and complexity in real-world networks, exploring the hidden communities has been a challenging task. Although a number of algorithms have been developed to address the community detection problem, still major concerns lie in scalability and consistency in the output. In this thesis, we have analyzed the topological features of various real-world networks and identified the functional groups corresponding to communities. Most of them are dependent on objective function based on a parameter such as modularity. However, it suffers from a problem known as resolution limit, where potential communities with few number of nodes could be missing in the result of community detection algorithm.
The first contribution of the thesis is on development of computational efficient community detection algorithm which is based on a new objective function known as MIN-MAX modularity. It can also be used for measuring the quality of community partition. Unlike other scoring metric, it does not exhibit the problem of resolution limit
The second contribution is based on development of distributed and scalable community detection algorithms which are able to handle the complexity and large size real-world networks. The proposed distributed algorithms are based on scale-free networks that exhibit power-law degree distribution which is often more resemble with the real-world networks
The third contribution is based on development of meta-heuristic solutions to tackle the community detection problem in complex network. We have used genetic algorithm and ant colony optimization techniques to develop the community detection algorithm. The major objective of the meta heuristic algorithms is to deliver the solution in less computational time, which will differ only by a constant factor from the optimal solution. The experimental analysis on some real-world and synthetic networks shows that it outperforms over other existing traditional community detection algorithms
The fourth contribution focuses on designing the scalable algorithms that identify the influential communities in the network. In order to explore the influential community, we have adopted three different approaches. First one is fuzzy and rough set theory, which capture the degree of uncertainty in belongingness of a node in the network. The second one is the centrality analysis. It has been observed that any social group or community usually formed from a central point. If we are able to capture the central node or influential nodes in the network, it would be easy to explore the hidden communities lying within it. However, as the real-world network’s size is huge and complex, processing it in traditional tools is quite challenging. We have developed map-reduce based algorithms for identifying the central nodes in the network. We have leveraged this central nodes in exploring the influential communities. The third one is based on the link prediction problem that identify the relationships between nodes, which are either missing or does not exist currently but likely to be appear in future. It has been observed that strength of ties has significant roles in community evolution in the network. It is desirable to quantify the strength of missing links, as the missing links may have the major contribution in forming the clusters in the network. To address this problem, map-reduce based scalable and distributed algorithms have been developed to identify and quantify the strength of the links.