April 25, 2017

Community Detection

A community is a structure which is densely intra-connected and sparsely inter-connected. Community Detection is the process of finding community in the given network.

Fig. 1 - Community

If there are group of nodes such that they are densely intraconnected and sparsely interconnected, then that network is said to have a structure within, known as community or a cluster. hence, community detection is the problem of detecting such group of nodes, known as communities.
Community detection is useful in:

  1. Social network
  2. Meta structure
  3. Protein interaction network
  4. Rumor spreading or epidemic spreading

Social network

Communities are eminent in Social networks , they appear in various forms such as community of friends, family, colleagues , etc. Aside from that , communities are also formed as per similar interests which may be useful for finding hierarchical nodes and better advertisement targeting.

Meta structure

Community Detection can be helpful to understand the overall nature of the graph and abstracting out the important details in the graph.

Protein interaction network

In Protein interaction network, communities corresponds to the group of proteins which perform similar actions.

Rumor spreading or epidemic spreading

Community detection can help in preventing the spread of rumour or help in controlling the spread of epidemic by detection of the inter-community links and taking precautionary measures.

There are various methods to detect community and most of them focus on the methods which tends to increase the modularity. Modularity is a quality factor which can be used to test a community detection algorithm performance and see how it performs against other community detection methods in terms of quality. Modularity is high when the community structure have high intra connectivity and less inter connectivity. In further posts we might discuss some of the community detection algorithms and try to understand how they work.