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 branchandcut scheme for solving the NPcomplete 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).