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:
- Social network
- Meta structure
- Protein interaction network
- Rumor spreading or epidemic spreading
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.
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.