r""" Partitioning a given graph with structure matrix :math:`\mathbf{C} \in R^{n \times n}` into `npart` partitions either 'random', or using one of {'louvain', 'fluid'} algorithms from networkx, or 'spectral' clustering from scikit-learn, or (Fused) Gromov-Wasserstein projections fr
(
C, npart, part_method="random", F=None, alpha=1.0, random_state=0, nx=None
)
| 274 | |
| 275 | |
| 276 | def get_graph_partition( |
| 277 | C, npart, part_method="random", F=None, alpha=1.0, random_state=0, nx=None |
| 278 | ): |
| 279 | r""" |
| 280 | Partitioning a given graph with structure matrix :math:`\mathbf{C} \in R^{n \times n}` |
| 281 | into `npart` partitions either 'random', or using one of {'louvain', 'fluid'} |
| 282 | algorithms from networkx, or 'spectral' clustering from scikit-learn, |
| 283 | or (Fused) Gromov-Wasserstein projections from POT. |
| 284 | |
| 285 | Parameters |
| 286 | ---------- |
| 287 | C : array-like, shape (n, n) |
| 288 | Structure matrix. |
| 289 | npart : int, |
| 290 | number of partitions/clusters smaller than the number of nodes in |
| 291 | :math:`\mathbf{C}`. |
| 292 | part_method : str, optional. Default is 'random'. |
| 293 | Partitioning algorithm to use among {'random', 'louvain', 'fluid', 'spectral', 'GW', 'FGW'}. |
| 294 | 'random' for random sampling of points; 'louvain' and 'fluid' for graph |
| 295 | partitioning algorithm that works well on adjacency matrix, If the |
| 296 | louvain algorithm is used, `npart` is ignored; 'spectral' for spectral |
| 297 | clustering; '(F)GW' for (F)GW projection using sr(F)GW solvers. |
| 298 | F : array-like, shape (n, d), optional. (Default is None) |
| 299 | Optional feature matrix aligned with the graph structure. Only used if |
| 300 | `part_method="FGW"`. |
| 301 | alpha : float, optional. (Default is 1.) |
| 302 | Trade-off parameter between feature and structure matrices, taking |
| 303 | values in [0, 1] and only used if `F != None` and `part_method="FGW"`. |
| 304 | random_state: int, optional |
| 305 | Random seed for the partitioning algorithm. |
| 306 | nx : backend, optional |
| 307 | POT backend. |
| 308 | |
| 309 | Returns |
| 310 | ------- |
| 311 | part : array-like, shape (npart,) |
| 312 | Array of partition assignment for each node. |
| 313 | |
| 314 | References |
| 315 | ---------- |
| 316 | .. [68] Chowdhury, S., Miller, D., & Needham, T. (2021). |
| 317 | Quantized gromov-wasserstein. ECML PKDD 2021. Springer International Publishing. |
| 318 | |
| 319 | """ |
| 320 | if nx is None: |
| 321 | nx = get_backend(C) |
| 322 | |
| 323 | n = C.shape[0] |
| 324 | C0 = C |
| 325 | |
| 326 | if (alpha != 1.0) and (F is None): |
| 327 | raise ValueError("`alpha != 1` but node features are not provided.") |
| 328 | |
| 329 | if npart >= n: |
| 330 | warnings.warn( |
| 331 | "Requested number of partitions higher than the number of nodes" |
| 332 | "hence we enforce each node to be a partition.", |
| 333 | stacklevel=2, |
no test coverage detected