Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.33 KB)

1
# -*- coding: utf-8 -*-
2
#
3
# Author: Yuto Yamaguchi <yuto.ymgc@gmail.com>
4
"""Function for computing Harmonic function algorithm by Zhu et al.
5

6
References
7
----------
8
Zhu, X., Ghahramani, Z., & Lafferty, J. (2003, August).
9
Semi-supervised learning using gaussian fields and harmonic functions.
10
In ICML (Vol. 3, pp. 912-919).
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__ = ['harmonic_function']
23

    
24

    
25
@not_implemented_for('directed')
26
def harmonic_function(G, max_iter=30, label_name='label'):
27
    """Node classification by Harmonic function
28

29
    Parameters
30
    ----------
31
    G : NetworkX Graph
32
    max_iter : int
33
        maximum number of iterations allowed
34
    label_name : string
35
        name of target labels to predict
36

37
    Raises
38
    ----------
39
    `NetworkXError` if no nodes on `G` has `label_name`.
40

41
    Returns
42
    ----------
43
    predicted : array, shape = [n_samples]
44
        Array of predicted labels
45

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

60
    References
61
    ----------
62
    Zhu, X., Ghahramani, Z., & Lafferty, J. (2003, August).
63
    Semi-supervised learning using gaussian fields and harmonic functions.
64
    In ICML (Vol. 3, pp. 912-919).
65
    """
66
    try:
67
        import numpy as np
68
    except ImportError:
69
        raise ImportError(
70
            "harmonic_function() requires numpy: http://scipy.org/ ")
71
    try:
72
        from scipy import sparse
73
    except ImportError:
74
        raise ImportError(
75
            "harmonic_function() requires scipy: http://scipy.org/ ")
76

    
77
    def _build_propagation_matrix(X, labels):
78
        """Build propagation matrix of Harmonic function
79

80
        Parameters
81
        ----------
82
        X : scipy sparse matrix, shape = [n_samples, n_samples]
83
            Adjacency matrix
84
        labels : array, shape = [n_samples, 2]
85
            Array of pairs of node id and label id
86

87
        Returns
88
        ----------
89
        P : scipy sparse matrix, shape = [n_samples, n_samples]
90
            Propagation matrix
91

92
        """
93
        degrees = X.sum(axis=0).A[0]
94
        degrees[degrees == 0] = 1  # Avoid division by 0
95
        D = sparse.diags((1.0 / degrees), offsets=0)
96
        P = D.dot(X).tolil()
97
        P[labels[:, 0]] = 0  # labels[:, 0] indicates IDs of labeled nodes
98
        return P
99

    
100
    def _build_base_matrix(X, labels, n_classes):
101
        """Build base matrix of Harmonic function
102

103
        Parameters
104
        ----------
105
        X : scipy sparse matrix, shape = [n_samples, n_samples]
106
            Adjacency matrix
107
        labels : array, shape = [n_samples, 2]
108
            Array of pairs of node id and label id
109
        n_classes : integer
110
            The number of classes (distinct labels) on the input graph
111

112
        Returns
113
        ----------
114
        B : array, shape = [n_samples, n_classes]
115
            Base matrix
116
        """
117
        n_samples = X.shape[0]
118
        B = np.zeros((n_samples, n_classes))
119
        B[labels[:, 0], labels[:, 1]] = 1
120
        return B
121

    
122
    X = nx.to_scipy_sparse_matrix(G)  # adjacency matrix
123
    labels, label_dict = _get_label_info(G, label_name)
124

    
125
    if labels.shape[0] == 0:
126
        raise nx.NetworkXError(
127
            "No node on the input graph is labeled by '" + label_name + "'.")
128

    
129
    n_samples = X.shape[0]
130
    n_classes = label_dict.shape[0]
131

    
132
    F = _init_label_matrix(n_samples, n_classes)
133

    
134
    P = _build_propagation_matrix(X, labels)
135
    B = _build_base_matrix(X, labels, n_classes)
136

    
137
    remaining_iter = max_iter
138
    while remaining_iter > 0:
139
        F = _propagate(P, F, B)
140
        remaining_iter -= 1
141

    
142
    predicted = _predict(F, label_dict)
143

    
144
    return predicted
145

    
146

    
147
def setup_module(module):
148
    """Fixture for nose tests."""
149
    from nose import SkipTest
150
    try:
151
        import numpy
152
    except ImportError:
153
        raise SkipTest("NumPy not available")
154
    try:
155
        import scipy
156
    except ImportError:
157
        raise SkipTest("SciPy not available")