Community detection in social networks

Abstract

A social network is a social structure made up of actors(such as individuals or organizations) and the dyadic ties between them. It can be represented by a graph with nodes representing the individuals and edges representing the interactions between them. For example scientists co-authoring a paper, employees of a company working on a common project. A community is formed by individuals such that those within a group interact with each other more frequently than with those outside the group. Community detection problem refers to the problem of finding such groups in real world social networks. A number of methods to address this problem have been proposed, and Newman distinguishes these into two categories: bottom-up sociological approaches and top-down computer science approaches. Basically I will be concentrating on modularity based methods to detect communitites in a social network. Modularity is a property of the network that measures when the division is good, in the sense that there are many edges within the community and only a few between them. In modularity based algorithms, each node of the graph is considered as an individual community and the communities are joined iteratively based on the increase in modularity caused by their joining. the ones producing maximum change in modularity are joined. In order to detect overlapping communities I have used methods such as clique percolation and SLPA. Clique percolation is based on the assumption that a community consists of fully connected subgraphs and detects overlapping communities by searching for adjacent cliques. SLPA mimics human pairwise communication behavior.