Modified Louvain¶

Modified Louvain implementation.

asunder.base.algorithms.louvain_modified.to_csr(A)¶

Convert array-like or sparse to CSR[float].

Parameters:: A (Any) – Array-like input.
Returns:: CSR matrix.
Return type:: sparse.csr_matrix of float

asunder.base.algorithms.louvain_modified.directed_to_undirected(A, average=True)¶

Symmetrize adjacency. If average=True, use 0.5*(A + A.T); else sum.

Parameters:

A (sparse.csr_matrix) – Input adjacency.
average (bool) – Enable / disable returning the average. Defaults to True.

Returns:

Symmetrized adjacency.

Return type:

sparse.csr_matrix

asunder.base.algorithms.louvain_modified.symmetrize(A, average=True)¶

Symmetrize adjacency. If average=True, use 0.5*(A + A.T); else sum.

Parameters:

A (sparse.csr_matrix) – Input parameter.
average (bool) – Input parameter.

Returns:

Computed result.

Return type:

sparse.csr_matrix

asunder.base.algorithms.louvain_modified.degrees(A)¶

Compute node degrees (sum of row).

Parameters:: A (sparse.csr_matrix, shape (N, N)) – Input CSR array.
Returns:: Node degrees.
Return type:: np.ndarray, shape (N,)

asunder.base.algorithms.louvain_modified.total_weight(A)¶

Compute total edge weight m for undirected graphs.

Parameters:: A (sparse.csr_matrix) – Input CSR array.
Returns:: total edge weight.
Return type:: float

asunder.base.algorithms.louvain_modified.get_membership(labels, n_labels=None)¶

Build a CSR membership indicator matrix of shape (n_nodes, n_labels).

Parameters:

labels (np.ndarray of int, shape (N,)) – Membership vector.
n_labels (Optional[int]) – Number of groups.

Returns:

membership indicator matrix.

Return type:

sparse.csr_matrix, shape (n_nodes, n_labels)

asunder.base.algorithms.louvain_modified.normalize_rows_csr(X)¶

Row L1-normalization for CSR. Zero rows remain zero.

Parameters:: X (sparse.csr_matrix) – Input matrix.
Returns:: L1-normalized matrix.
Return type:: sparse.csr_matrix

asunder.base.algorithms.louvain_modified.reindex_consecutive(labels)¶

Map arbitrary non-negative labels to 0..k-1 preserving order of first occurrence.

Parameters:: labels (np.ndarray of int, shape (N,)) – Community assignment vector.
Returns:: Reindexed community assignment vector.
Return type:: np.ndarray of int, shape (N,)

class asunder.base.algorithms.louvain_modified.ModifiedLouvain(resolution=1.0, tol_optimization=0.001, tol_aggregation=0.001, n_aggregations=-1, random_state=None, symmetrize_average=True)¶

Bases: object

Full Louvain with resolution parameter and multi-level aggregation. Also exposes a one-level ‘modified fast unfolding’ path with dual-adjusted modularity.

Parameters:

resolution (float) – Modularity resolution γ.
tol_optimization (float) – Minimum modularity increase to keep optimizing at a level.
tol_aggregation (float) – Minimum modularity increase to perform another aggregation.
n_aggregations (int) – Maximum number of aggregation levels (-1 means unlimited).
random_state (Optional[int]) – Seed for node shuffling inside local moving.
symmetrize_average (bool) – If True, symmetrize directed inputs by averaging; otherwise by summation.

labels_¶

Final labels for original nodes (reindexed to 0..k-1).

Type:: np.ndarray of int, shape (N,)

probs_¶

Row-normalized neighbor-mass per cluster on the ORIGINAL graph.

Type:: scipy.sparse.csr_matrix

aggregate_¶

Last-level aggregated adjacency.

Type:: scipy.sparse.csr_matrix

modularity_¶

Final modularity value (Newman-Girvan with resolution γ).

Type:: float

obj_val_¶

Subproblem objective.

Type:: Optional[float]

fit(input_matrix, duals, a=None, mprime=None)¶

Run multi-level Louvain using dual-adjusted objective.

Parameters:

input_matrix (array-like or sparse, shape (N, N)) – Square adjacency. Directed inputs are symmetrized.
duals (Dict[str, np.ndarray or float]) – Dual terms used to modify the community detection objective. 2D, 1D and scalar dual values are supported. Missing entries are treated as zeros.
a (Optional[np.ndarray], shape (N,)) – Degree-like vector; defaults to row sums of the symmetrized adjacency.
mprime (Optional[float]) – Sum of degrees; defaults to sum(a).

Returns:

Fitted estimator instance.

Return type:

ModifiedLouvain

fit_standard_louvain(input_matrix)¶

Run multi-level Louvain on an undirected weighted graph.

Parameters:: input_matrix (sequence[sequence[int or float]]) – Input sequence; typically adjacency like.
Returns:: Fitted estimator instance.
Return type:: ModifiedLouvain

predict()¶

Predict.

Returns:: Returns 1D communtiy labels.
Return type:: np.ndarray of int, shape (N,)

transform()¶

Returns random-walk confidence scores, if generated.

Returns:: Returns random-walk confidence scores.
Return type:: sparse.csr_matrix

predict_proba()¶

Wraps self.transform and converts the CSR matrix to a numpy array.

Returns:: Returns probability values as an array.
Return type:: np.ndarray of int, shape (N, K)

fit_modified_one_level(input_matrix, duals, a=None, m=None, max_iter=100, tol=1e-06)¶

Run a single-level greedy improvement using a dual-adjusted modularity matrix.

This updates labels_ and probs_ on the original nodes and stores obj_val_ when dual scalars are provided.

Parameters:

input_matrix (sequence[sequence[int or float]]) – Input sequence; adjacency-like.
duals (Dict[str, np.ndarray or float]) – Dual terms used to modify the community detection objective. 2D, 1D and scalar dual values are supported. Missing entries are treated as zeros.
a (Optional[np.ndarray], shape (N,)) – Degree-like vector; defaults to row sums of the symmetrized adjacency.
m (Optional[float]) – Sum of degrees; defaults to sum(a).
max_iter (int) – Maximum number of iterations.
tol (float) – Numerical tolerance.

Returns:

Fitted estimator instance.

Return type:

ModifiedLouvain

_local_move(A, rng)¶

Local moving phase on a single level using the standard Louvain gain with resolution.

Parameters:

A (sparse.csr_matrix, shape (N, N)) – Input adjacency / weight matrix.
rng (np.random.RandomState) – random state.

Return type:

Tuple[ndarray, float]

Returns:

labels (np.ndarray of int, shape (N,)) – Community assignment vector.
Q (float) – Modularity value.

static _aggregate_graph(A, labels)¶

Aggregate adjacency: A’ = M^T A M.

Parameters:

A (sparse.csr_matrix, shape (N, N)) – Input adjacency / weight matrix.
labels (np.ndarray of int, shape (N,)) – Community assignment vector.

Returns:

Aggregated adjacency.

Return type:

sparse.csr_matrix, shape (N, N)

static _modularity(A, labels, k, m, gamma)¶

Compute Newman-Girvan modularity with resolution γ.

Parameters:

A (sparse.csr_matrix, shape (N, N)) – Input adjacency.
labels (np.ndarray of int, shape (N,)) – Community assignment vector.
k (np.ndarray of int | float, shape (N,)) – Degree vector.
m (float) – Total graph weight, computed as sum(A) / 2.
gamma (float) – Resolution parameter for computing modularity.

Returns:

Computed result.

Return type:

float

static _build_modified_modularity(A, a, m, duals)¶

Construct dense modified modularity matrix.

Parameters:

A (sparse.csr_matrix, shape (N, N)) – Input adjacency.
a (np.ndarray of int | float, shape (N,)) – Degree vector.
m (float) – Twice the total graph weight, computed as sum(A).
duals (Dict[str, np.ndarray or float]) – Dual terms used to modify the community detection objective. 2D and 1D dual values are supported.

Returns:

mm – Modified modularity matrix.

Return type:

np.ndarray of float, shape (N, N)

static _one_level_fast_unfolding(A, mm, rng, max_iter=100, tol=1e-06)¶

Greedy local improvement using mm for scoring.

Parameters:

A (sparse.csr_matrix, shape (N, N)) – Input adjacency / weight matrix.
mm (np.ndarray of float, shape (N, N)) – Modified modularity matrix.
rng (np.random.RandomState) – Random state.
max_iter (int) – Maximum number of iterations.
tol (float) – Numerical tolerance.

Returns:

labels – Community assignment vector.

Return type:

np.ndarray of int, shape (N,)

static _assemble_S(duals, n)¶

Symmetric matrix S, aggregated from dual components; zeros if missing.

Parameters:

duals (Dict[str, np.ndarray or float]) – Dual terms used to modify the community detection objective. 2D and 1D dual values are supported.
n (int) – Number of nodes.

Returns:

S – Aggregated dual matrix.

Return type:

np.ndarray of float, shape (N, N)

static _build_M(A, a, mprime, gamma, S)¶

Dense effective modularity matrix. M = A / m’ - γ * (a a^T) / (m’^2) - S

Parameters:

A (sparse.csr_matrix, shape (N, N)) – Input adjacency / weight matrix.
a (np.ndarray of int or float, shape (N,)) – Degree-like vector; defaults to row sums of the symmetrized adjacency.
mprime (float) – Sum of degrees; defaults to sum(a).
gamma (float) – Modularity resolution parameter.
S (np.ndarray of float, shape (N, N)) – Aggregated 2D dual matrix.

Returns:

M – Modified modularity matrix.

Return type:

np.ndarray of float, shape (N, N)

_local_move_with_duals(A, S, a, mprime, gamma, rng)¶

Local moving with dual-adjusted objective, like-for-like with Blondel ΔQ when S == 0.

Parameters:

A (sparse.csr_matrix, shape (N, N)) – Input adjacency / weight matrix.
S (np.ndarray of float, shape (N, N)) – Aggregated 2D dual matrix.
a (np.ndarray of int or float, shape (N,)) – Degree-like vector; defaults to row sums of the symmetrized adjacency.
mprime (float) – Sum of degrees; defaults to sum(a).
gamma (float) – Modularity resolution parameter.
rng (np.random.RandomState) – Random state.

Return type:

Tuple[ndarray, float]

Returns:

labels (np.ndarray of int, shape (N,)) – Community assignment vector.
final_obj (float) – Final modularity score.

static _objective_from_partition(Mmat, labels)¶

sum_{i,j in same cluster} M_ij computed via block sums.

Parameters:

Mmat (np.ndarray of float, shape (N, N)) – Modified modularity matrix.
labels (np.ndarray of int, shape (N,)) – Community assignment labels.

Returns:

Modularity score.

Return type:

float

static _block_sum(mm, membership)¶

Computing block summation which gives the modularity score.

Parameters:

mm (np.ndarray of float, shape (N, N)) – Modified modularity matrix.
membership (sparse.csr_matrix) – Membership CSR matrix.

Returns:

Block sum result.

Return type:

float