Defining and Evaluating Network Communities Based on Ground-Truth in Online Social Networks

摘要

A social network is a cluster or aggregation of vertices such as persons or social entities, and edges which are used to depict personal relationship between these nodes. Social networks have a noteworthy role in the movement of data, and social network exploration has gained a focus in research. The analysis of these social networks has resulted into uncovering of variety of communities in the network. The main objective of uncovering the structure of a community is to break the network into dense areas of the graph, and these dense areas represent entities which are related closely and hence they belong to a community. Plentiful algorithms have been suggested and recommended, and surveys have been conducted currently. In this manuscript, we will discuss numerous strategies for uncovering the structure of communities and techniques which have been suggested so far. We will divide these algorithms into several categories. These categories correspond to traditional approach of community detection, overlapping community detection, established clustering techniques for uncovering the structure of communities, nonclique-based techniques for uncovering the structure of communities, community detection using genetic algorithms, improved modularity approach for uncovering the structure of communities and so forth. We will start by discussing and understanding several metrics which can be used to ascertain the structure and hence the quality of communities. We will also compare all these community detection algorithms based on approaches used, along with parameters these algorithms depend on.