Source code for sknetwork.classification.propagation

#!/usr/bin/env python3
# coding: utf-8
"""
Created on April 2020
@author: Thomas Bonald <tbonald@enst.fr>
"""

from typing import Union

import numpy as np
from scipy import sparse

from sknetwork.classification.base import BaseClassifier
from sknetwork.classification.vote import vote_update
from sknetwork.linalg.normalization import normalize
from sknetwork.utils.format import get_adjacency_values
from sknetwork.utils.membership import get_membership


[docs]class Propagation(BaseClassifier): """Node classification by label propagation. Parameters ---------- n_iter : float Maximum number of iterations (-1 for infinity). node_order : str * `'random'`: node labels are updated in random order. * `'increasing'`: node labels are updated by increasing order of (in-)weight. * `'decreasing'`: node labels are updated by decreasing order of (in-)weight. * Otherwise, node labels are updated by index order. weighted : bool If ``True``, the vote of each neighbor is proportional to the edge weight. Otherwise, all votes have weight 1. Attributes ---------- labels_ : np.ndarray, shape (n_labels,) Label of each node. probs_ : sparse.csr_matrix, shape (n_row, n_labels) Probability distribution over labels. labels_row_, labels_col_ : np.ndarray Labels of rows and columns, for bipartite graphs. probs_row_, probs_col_ : sparse.csr_matrix, shape (n_row, n_labels) Probability distributions over labels for rows and columns (for bipartite graphs). Example ------- >>> from sknetwork.classification import Propagation >>> from sknetwork.data import karate_club >>> propagation = Propagation() >>> graph = karate_club(metadata=True) >>> adjacency = graph.adjacency >>> labels_true = graph.labels >>> labels = {0: labels_true[0], 33: labels_true[33]} >>> labels_pred = propagation.fit_predict(adjacency, labels) >>> np.round(np.mean(labels_pred == labels_true), 2) 0.94 References ---------- Raghavan, U. N., Albert, R., & Kumara, S. (2007). `Near linear time algorithm to detect community structures in large-scale networks. <https://arxiv.org/pdf/0709.2938.pdf>`_ Physical review E, 76(3), 036106. """ def __init__(self, n_iter: float = -1, node_order: str = None, weighted: bool = True): super(Propagation, self).__init__() if n_iter < 0: self.n_iter = np.inf else: self.n_iter = n_iter self.node_order = node_order self.weighted = weighted @staticmethod def _instantiate_vars(labels: np.ndarray): """Instantiate variables for label propagation.""" n = len(labels) if len(set(labels)) == n: index_seed = np.arange(n) index_remain = np.arange(n) else: index_seed = np.argwhere(labels >= 0).ravel() index_remain = np.argwhere(labels < 0).ravel() labels = labels[index_seed] return index_seed.astype(np.int32), index_remain.astype(np.int32), labels.astype(np.int32)
[docs] def fit(self, input_matrix: Union[sparse.csr_matrix, np.ndarray], labels: Union[np.ndarray, dict] = None, labels_row: Union[np.ndarray, dict] = None, labels_col: Union[np.ndarray, dict] = None) -> 'Propagation': """Node classification by label propagation. Parameters ---------- input_matrix : Adjacency matrix or biadjacency matrix of the graph. labels : Known labels (dictionary or array). Negative values ignored. labels_row, labels_col : Known labels of rows and columns (for bipartite graphs). Returns ------- self: :class:`Propagation` """ adjacency, seeds, self.bipartite = get_adjacency_values(input_matrix, values=labels, values_row=labels_row, values_col=labels_col, which='labels') n = adjacency.shape[0] index_seed, index_remain, labels_seed = self._instantiate_vars(seeds) if self.node_order == 'random': np.random.shuffle(index_remain) elif self.node_order == 'decreasing': index = np.argsort(-adjacency.T.dot(np.ones(n))).astype(np.int32) index_remain = index[index_remain] elif self.node_order == 'increasing': index = np.argsort(adjacency.T.dot(np.ones(n))).astype(np.int32) index_remain = index[index_remain] labels = -np.ones(n, dtype=np.int32) labels[index_seed] = labels_seed labels_remain = np.zeros_like(index_remain, dtype=np.int32) indptr = adjacency.indptr.astype(np.int32) indices = adjacency.indices.astype(np.int32) if self.weighted: data = adjacency.data.astype(np.float32) else: data = np.ones(n, dtype=np.float32) t = 0 while t < self.n_iter and not np.array_equal(labels_remain, labels[index_remain]): t += 1 labels_remain = labels[index_remain].copy() labels = np.asarray(vote_update(indptr, indices, data, labels, index_remain)) probs = get_membership(labels) probs = normalize(adjacency.dot(probs)) self.labels_ = labels self.probs_ = probs self._split_vars(input_matrix.shape) return self