Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / node_classification / lgc.py @ 5cef0f13

History | View | Annotate | Download (4.71 KB)

1
# -*- coding: utf-8 -*-
2
#
3
# Author: Yuto Yamaguchi <yuto.ymgc@gmail.com>
4
"""Function for computing Local and global consistency algorithm by Zhou et al.
5

6
References
7
----------
8
Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schölkopf, B. (2004).
9
Learning with local and global consistency.
10
Advances in neural information processing systems, 16(16), 321-328.
11
"""
12
import networkx as nx
13

    
14
from networkx.utils.decorators import not_implemented_for
15
from networkx.algorithms.node_classification.utils import (
16
    _get_label_info,
17
    _init_label_matrix,
18
    _propagate,
19
    _predict,
20
)
21

    
22
__all__ = ['local_and_global_consistency']
23

    
24

    
25
@not_implemented_for('directed')
26
def local_and_global_consistency(G, alpha=0.99,
27
                                 max_iter=30,
28
                                 label_name='label'):
29
    """Node classification by Local and Global Consistency
30

31
    Parameters
32
    ----------
33
    G : NetworkX Graph
34
    alpha : float
35
        Clamping factor
36
    max_iter : int
37
        Maximum number of iterations allowed
38
    label_name : string
39
        Name of target labels to predict
40

41
    Raises
42
    ----------
43
    `NetworkXError` if no nodes on `G` has `label_name`.
44

45
    Returns
46
    ----------
47
    predicted : array, shape = [n_samples]
48
        Array of predicted labels
49

50
    Examples
51
    --------
52
    >>> from networkx.algorithms import node_classification
53
    >>> G = nx.path_graph(4)
54
    >>> G.node[0]['label'] = 'A'
55
    >>> G.node[3]['label'] = 'B'
56
    >>> G.nodes(data=True)
57
    NodeDataView({0: {'label': 'A'}, 1: {}, 2: {}, 3: {'label': 'B'}})
58
    >>> G.edges()
59
    EdgeView([(0, 1), (1, 2), (2, 3)])
60
    >>> predicted = node_classification.local_and_global_consistency(G)
61
    >>> predicted
62
    ['A', 'A', 'B', 'B']
63

64

65
    References
66
    ----------
67
    Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schölkopf, B. (2004).
68
    Learning with local and global consistency.
69
    Advances in neural information processing systems, 16(16), 321-328.
70
    """
71
    try:
72
        import numpy as np
73
    except ImportError:
74
        raise ImportError(
75
            "local_and_global_consistency() requires numpy: ",
76
            "http://scipy.org/ ")
77
    try:
78
        from scipy import sparse
79
    except ImportError:
80
        raise ImportError(
81
            "local_and_global_consistensy() requires scipy: ",
82
            "http://scipy.org/ ")
83

    
84
    def _build_propagation_matrix(X, labels, alpha):
85
        """Build propagation matrix of Local and global consistency
86

87
        Parameters
88
        ----------
89
        X : scipy sparse matrix, shape = [n_samples, n_samples]
90
            Adjacency matrix
91
        labels : array, shape = [n_samples, 2]
92
            Array of pairs of node id and label id
93
        alpha : float
94
            Clamping factor
95

96
        Returns
97
        ----------
98
        S : scipy sparse matrix, shape = [n_samples, n_samples]
99
            Propagation matrix
100

101
        """
102
        degrees = X.sum(axis=0).A[0]
103
        degrees[degrees == 0] = 1  # Avoid division by 0
104
        D2 = np.sqrt(sparse.diags((1.0 / degrees), offsets=0))
105
        S = alpha * D2.dot(X).dot(D2)
106
        return S
107

    
108
    def _build_base_matrix(X, labels, alpha, n_classes):
109
        """Build base matrix of Local and global consistency
110

111
        Parameters
112
        ----------
113
        X : scipy sparse matrix, shape = [n_samples, n_samples]
114
            Adjacency matrix
115
        labels : array, shape = [n_samples, 2]
116
            Array of pairs of node id and label id
117
        alpha : float
118
            Clamping factor
119
        n_classes : integer
120
            The number of classes (distinct labels) on the input graph
121

122
        Returns
123
        ----------
124
        B : array, shape = [n_samples, n_classes]
125
            Base matrix
126
        """
127

    
128
        n_samples = X.shape[0]
129
        B = np.zeros((n_samples, n_classes))
130
        B[labels[:, 0], labels[:, 1]] = 1 - alpha
131
        return B
132

    
133
    X = nx.to_scipy_sparse_matrix(G)  # adjacency matrix
134
    labels, label_dict = _get_label_info(G, label_name)
135

    
136
    if labels.shape[0] == 0:
137
        raise nx.NetworkXError(
138
            "No node on the input graph is labeled by '" + label_name + "'.")
139

    
140
    n_samples = X.shape[0]
141
    n_classes = label_dict.shape[0]
142
    F = _init_label_matrix(n_samples, n_classes)
143

    
144
    P = _build_propagation_matrix(X, labels, alpha)
145
    B = _build_base_matrix(X, labels, alpha, n_classes)
146

    
147
    remaining_iter = max_iter
148
    while remaining_iter > 0:
149
        F = _propagate(P, F, B)
150
        remaining_iter -= 1
151

    
152
    predicted = _predict(F, label_dict)
153

    
154
    return predicted
155

    
156

    
157
def setup_module(module):
158
    """Fixture for nose tests."""
159
    from nose import SkipTest
160
    try:
161
        import numpy
162
    except ImportError:
163
        raise SkipTest("NumPy not available")
164
    try:
165
        import scipy
166
    except ImportError:
167
        raise SkipTest("SciPy not available")