Community Detection

Community Detection

Illustration of overlapping communities
Gergelypalla [Public domain], from Wikimedia Commons

In Complex networks, a network is said to have a community structure if there are group of nodes such that those node have dense connection in the group and sparse connection between other group or other nodes. If such a structure exists in a network, then that network is said to contain a community in it. The problem of detecting such structures is coined as community detection. Community detection is useful in:
1. Social Network
2. Meta Structure
3. Protein Interaction Network
4. Rumour 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. 

Rumour 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.

Written By, 
Sarvesh Bhatnagar

Popular Posts