Local Community Detection in Social Networks

Recent years have witnessed the rapid growth of social network services and consequently research problems investigated in this area. Community detection is one of the most important problems in social networks. A good community can be defined as a group of vertices that are highly connected and loosely connected to the vertices outside the group. Community detection includes exploring the community partitioning in social networks. Regarding the fact that social networks are huge, having complete information about the whole network is almost impossible. As a result, the problem of local community detection has become more popular in recent years. This problem can be defined as the detection of a community for a given node by using local information. It is noteworthy that the focus of this study is on the problem of local community detection. One major question to the problem of community detection is how to assess different communities. The most widely used technique to evaluate the quality of communities is to compare them with ground-truth communities. However, for many networks, the ground-truth communities are not known. As a result, it is necessary to have a comprehensive metric to evaluate the quality of communities. In this study, a local quality metric noted as GDM is proposed, several local community detection algorithms are compared by assessing their detected communities. The experimental results, illustrate that the local community detection algorithms are fairly compared using GDM. It is also discussed how GDM covers the drawbacks of other existing local metrics. Moreover, it is shown that the judgment of GDM is almost the same as that of the F-score, i.e. the metric which compares the community with its ground-truth community. Furthermore, a new metric, called P, and a new local community detection algorithm, Alg P are proposed. To detect communities locally, researchers mostly utilize an evaluation metric along with an algorithm to explore communities. The proposed algorithm includes three different steps in which relevant nodes are added in the first step and irrelevant nodes are removed in the second and third steps. It should be mentioned that at each iteration, more than one node is added to the community. Thus, the algorithm is terminated faster than the other algorithms with near-complexity. Regarding the experimental results, it is shown that the proposed algorithm outperforms state-of-the-art local community detection algorithms. Real-world social networks are dynamic and change over time. In order to model dynamic social networks, network history is partitioned into a series of snapshots, each one of which shows the state of the network at a time. Regarding dynamic networks, the problem of local community detection is not widely investigated. In this concern, a dynamic local community detection algorithm noted as DevDynaP, is proposed. The main feature of the proposed algorithm is that it starts from a given node, explores the network incrementally, and detects communities simultaneously at each snapshot. The experimental results show that the community partitioning resulting from the proposed dynamic algorithm outperforms that of the other compared algorithm. Also, the proposed algorithm explores the network faster than the compared algorithm. Many networks contain both positive and negative relations. A community in signed networks is defined as a group of nodes that are densely connected by positive links within the community and negative links between communities. Considering the problem of local community detection in signed networks, a new algorithm, noted as Alg SP, is developed by extending the metric $P$ for signed networks. Experimental results show that the proposed algorithm can detect the ground-truth communities independently from the starting nodes