Skip to main content

Community Detection

Description​

The notion of community in a graph is analogous to the real-world notion of community. Social circles are an example that is easy to see both on graphs and in the real world. A graph community can be defined as a partition of a graph, i.e. a set of nodes. M. Girvan and M. E. J. Newman argue that within a community, nodes are more strongly connected (more edges) to one another than to nodes in different communities.

drawing

Community detection assigns each node to a community. In this graph, each community's nodes are labeled with a distinct color.

There are various approaches to community detection. Among the most common algorithms there are the following:

  • Louvain method - based on modularity optimization; measures network connectivity within a community,
  • Leiden method - adjustment of the Louvain algorithm that introduces one level of refinement and brings together strongly connected communities,
  • Label propagation —a machine learning technique that assigns labels to unmarked nodes and modifies them with respect to neighbors.

Materials​

Implementation​

Community Detection

Community Detection

Community Detection

Dynamic Community Detection with the Louvain algorithm is implemented as part of the MAGE project. Be sure to check it out at the above link. ☝️

Use cases​

Finance

A natural usage of community detection is in the finance industry. Fraudsters often think alike, and act in criminal rings, which enables them to be more efficient. However, such rings can easily be discovered with community detection methods from their interactions and shared traits/resources.

Social networks

Terrorist groups are one of the biggest threats in today's society. Such groups can organize their activities through social media channels. Once one of the users is exposed as a potential threat, others can be revealed by analyzing their community on social networks.

Interests are usually shared within the community. To target a specific audience, community detection can be used to recommend certain products among users that are sharing interests.

Retail

The methods stated above under Social networks application can be applied in the retail industry. Targeting a product lineup to like-minded consumers has been crucial in retail marketing.