cdlib.algorithms.bayan

bayan(g_original: object, threshold: float = 0.001, time_allowed: int = 60, resolution: float = 1) → cdlib.classes.node_clustering.NodeClustering

The Bayan algorithm is community detection method that is capable of providing a globally optimal solution to the modularity maximization problem. Bayan can also be implemented such that it provides an approximation of the maximum modularity with a guarantee of proximity. This algorithm is theoretically grounded by the Integer Programming (IP) formulation of the modularity maximization problem and relies on an exact branch-and-cut scheme for solving the NP-complete optimization problem to global optimality.

The algorithm is integrated as an optional feature in CDlib due to its dependency on the Gurobi solver. For a detailed description on how to satisfy such a dependency please refer to the instructions provided in the official documentation: https://github.com/saref/bayan

Supported Graph Types

Undirected	Directed	Weighted
Yes	No	Yes

Parameters:

• g_original – a networkx/igraph object
• threshold – Threshold is the minimum optimality gap that Bayan should execute till. In the above example if Bayan finds a solution with modularity within 0.001 of the optimal solution, it will return that solution.
• time_allowed – Time allowed is the maximum time in seconds that Bayan should execute for.
• resolution – Resolution is the resolution parameter of the modularity function.

Returns:

NodeClustering object

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> com = algorithms.bayan(G)

References:

Aref, Samin, Hriday Chheda, and Mahdi Mostajabdaveh. “The Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity.” arXiv preprint arXiv:2209.04562 (2022).