Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / isomorphism / temporalisomorphvf2.py @ 5cef0f13

History | View | Annotate | Download (10.2 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
*****************************
4
Time-respecting VF2 Algorithm
5
*****************************
6

7
An extension of the VF2 algorithm for time-respecting graph ismorphism
8
testing in temporal graphs.
9

10
A temporal graph is one in which edges contain a datetime attribute,
11
denoting when interaction occurred between the incident nodes. A
12
time-respecting subgraph of a temporal graph is a subgraph such that
13
all interactions incident to a node occurred within a time threshold,
14
delta, of each other. A directed time-respecting subgraph has the
15
added constraint that incoming interactions to a node must precede
16
outgoing interactions from the same node - this enforces a sense of
17
directed flow.
18

19
Introduction
20
------------
21

22
The TimeRespectingGraphMatcher and TimeRespectingDiGraphMatcher
23
extend the GraphMatcher and DiGraphMatcher classes, respectively,
24
to include temporal constraints on matches. This is achieved through
25
a semantic check, via the semantic_feasibility() function.
26

27
As well as including G1 (the graph in which to seek embeddings) and
28
G2 (the subgraph structure of interest), the name of the temporal
29
attribute on the edges and the time threshold, delta, must be supplied
30
as arguments to the matching constructors.
31

32
A delta of zero is the strictest temporal constraint on the match -
33
only embeddings in which all interactions occur at the same time will
34
be returned. A delta of one day will allow embeddings in which
35
adjacent interactions occur up to a day apart.
36

37
Examples
38
--------
39

40
Examples will be provided when the datetime type has been incorporated.
41

42

43
Temporal Subgraph Isomorphism
44
-----------------------------
45

46
A brief discussion of the somewhat diverse current literature will be
47
included here.
48

49
References
50
----------
51

52
[1] Redmond, U. and Cunningham, P. Temporal subgraph isomorphism. In:
53
The 2013 IEEE/ACM International Conference on Advances in Social
54
Networks Analysis and Mining (ASONAM). Niagara Falls, Canada; 2013:
55
pages 1451 - 1452. [65]
56

57
For a discussion of the literature on temporal networks:
58

59
[3] P. Holme and J. Saramaki. Temporal networks. Physics Reports,
60
519(3):97–125, 2012.
61

62
Notes
63
-----
64

65
Handles directed and undirected graphs and graphs with parallel edges.
66

67
"""
68

    
69
from __future__ import absolute_import
70
import networkx as nx
71
from datetime import datetime, timedelta
72
from .isomorphvf2 import GraphMatcher, DiGraphMatcher
73

    
74
__all__ = ['TimeRespectingGraphMatcher',
75
           'TimeRespectingDiGraphMatcher']
76

    
77

    
78
class TimeRespectingGraphMatcher(GraphMatcher):
79

    
80
    def __init__(self, G1, G2, temporal_attribute_name, delta):
81
        """Initialize TimeRespectingGraphMatcher.
82

83
        G1 and G2 should be nx.Graph or nx.MultiGraph instances.
84

85
        Examples
86
        --------
87
        To create a TimeRespectingGraphMatcher which checks for
88
        syntactic and semantic feasibility:
89

90
        >>> from networkx.algorithms import isomorphism
91
        >>> G1 = nx.Graph(nx.path_graph(4, create_using=nx.Graph()))
92

93
        >>> G2 = nx.Graph(nx.path_graph(4, create_using=nx.Graph()))
94

95
        >>> GM = isomorphism.TimeRespectingGraphMatcher(G1, G2, 'date', timedelta(days=1))
96
        """
97
        self.temporal_attribute_name = temporal_attribute_name
98
        self.delta = delta
99
        super(TimeRespectingGraphMatcher, self).__init__(G1, G2)
100

    
101
    def one_hop(self, Gx, Gx_node, neighbors):
102
        """
103
        Edges one hop out from a node in the mapping should be
104
        time-respecting with respect to each other.
105
        """
106
        dates = []
107
        for n in neighbors:
108
            if type(Gx) == type(nx.Graph()):  # Graph G[u][v] returns the data dictionary.
109
                dates.append(Gx[Gx_node][n][self.temporal_attribute_name])
110
            else:  # MultiGraph G[u][v] returns a dictionary of key -> data dictionary.
111
                for edge in Gx[Gx_node][n].values():  # Iterates all edges between node pair.
112
                    dates.append(edge[self.temporal_attribute_name])
113
        if any(x is None for x in dates):
114
            raise ValueError('Datetime not supplied for at least one edge.')
115
        return not dates or max(dates) - min(dates) <= self.delta
116

    
117
    def two_hop(self, Gx, core_x, Gx_node, neighbors):
118
        """
119
        Paths of length 2 from Gx_node should be time-respecting.
120
        """
121
        return all(self.one_hop(Gx, v, [n for n in Gx[v] if n in core_x] + [Gx_node]) for v in neighbors)
122

    
123
    def semantic_feasibility(self, G1_node, G2_node):
124
        """Returns True if adding (G1_node, G2_node) is semantically
125
        feasible.
126

127
        Any subclass which redefines semantic_feasibility() must
128
        maintain the self.tests if needed, to keep the match() method
129
        functional. Implementations should consider multigraphs.
130
        """
131
        neighbors = [n for n in self.G1[G1_node] if n in self.core_1]
132
        if not self.one_hop(self.G1, G1_node, neighbors):  # Fail fast on first node.
133
            return False
134
        if not self.two_hop(self.G1, self.core_1, G1_node, neighbors):
135
            return False
136
        # Otherwise, this node is semantically feasible!
137
        return True
138

    
139

    
140
class TimeRespectingDiGraphMatcher(DiGraphMatcher):
141

    
142
    def __init__(self, G1, G2, temporal_attribute_name, delta):
143
        """Initialize TimeRespectingDiGraphMatcher.
144

145
        G1 and G2 should be nx.DiGraph or nx.MultiDiGraph instances.
146

147
        Examples
148
        --------
149
        To create a TimeRespectingDiGraphMatcher which checks for
150
        syntactic and semantic feasibility:
151

152
        >>> from networkx.algorithms import isomorphism
153
        >>> G1 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph()))
154

155
        >>> G2 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph()))
156

157
        >>> GM = isomorphism.TimeRespectingDiGraphMatcher(G1, G2, 'date', timedelta(days=1))
158
        """
159
        self.temporal_attribute_name = temporal_attribute_name
160
        self.delta = delta
161
        super(TimeRespectingDiGraphMatcher, self).__init__(G1, G2)
162

    
163
    def get_pred_dates(self, Gx, Gx_node, core_x, pred):
164
        """
165
        Get the dates of edges from predecessors.
166
        """
167
        pred_dates = []
168
        if type(Gx) == type(nx.DiGraph()):  # Graph G[u][v] returns the data dictionary.
169
            for n in pred:
170
                pred_dates.append(Gx[n][Gx_node][self.temporal_attribute_name])
171
        else:  # MultiGraph G[u][v] returns a dictionary of key -> data dictionary.
172
            for n in pred:
173
                for edge in Gx[n][Gx_node].values():  # Iterates all edge data between node pair.
174
                    pred_dates.append(edge[self.temporal_attribute_name])
175
        return pred_dates
176

    
177
    def get_succ_dates(self, Gx, Gx_node, core_x, succ):
178
        """
179
        Get the dates of edges to successors.
180
        """
181
        succ_dates = []
182
        if type(Gx) == type(nx.DiGraph()):  # Graph G[u][v] returns the data dictionary.
183
            for n in succ:
184
                succ_dates.append(Gx[Gx_node][n][self.temporal_attribute_name])
185
        else:  # MultiGraph G[u][v] returns a dictionary of key -> data dictionary.
186
            for n in succ:
187
                for edge in Gx[Gx_node][n].values():  # Iterates all edge data between node pair.
188
                    succ_dates.append(edge[self.temporal_attribute_name])
189
        return succ_dates
190

    
191
    def one_hop(self, Gx, Gx_node, core_x, pred, succ):
192
        """
193
        The ego node.
194
        """
195
        pred_dates = self.get_pred_dates(Gx, Gx_node, core_x, pred)
196
        succ_dates = self.get_succ_dates(Gx, Gx_node, core_x, succ)
197
        return self.test_one(pred_dates, succ_dates) and self.test_two(pred_dates, succ_dates)
198

    
199
    def two_hop_pred(self, Gx, Gx_node, core_x, pred):
200
        """
201
        The predeccessors of the ego node.
202
        """
203
        return all(self.one_hop(Gx, p, core_x, self.preds(Gx, core_x, p), self.succs(Gx, core_x, p, Gx_node)) for p in pred)
204

    
205
    def two_hop_succ(self, Gx, Gx_node, core_x, succ):
206
        """
207
        The successors of the ego node.
208
        """
209
        return all(self.one_hop(Gx, s, core_x, self.preds(Gx, core_x, s, Gx_node), self.succs(Gx, core_x, s)) for s in succ)
210

    
211
    def preds(self, Gx, core_x, v, Gx_node=None):
212
        pred = [n for n in Gx.predecessors(v) if n in core_x]
213
        if Gx_node:
214
            pred.append(Gx_node)
215
        return pred
216

    
217
    def succs(self, Gx, core_x, v, Gx_node=None):
218
        succ = [n for n in Gx.successors(v) if n in core_x]
219
        if Gx_node:
220
            succ.append(Gx_node)
221
        return succ
222

    
223
    def test_one(self, pred_dates, succ_dates):
224
        """
225
        Edges one hop out from Gx_node in the mapping should be
226
        time-respecting with respect to each other, regardless of
227
        direction.
228
        """
229
        time_respecting = True
230
        dates = pred_dates + succ_dates
231

    
232
        if any(x is None for x in dates):
233
            raise ValueError('Date or datetime not supplied for at least one edge.')
234

    
235
        dates.sort()  # Small to large.
236
        if 0 < len(dates) and not (dates[-1] - dates[0] <= self.delta):
237
            time_respecting = False
238
        return time_respecting
239

    
240
    def test_two(self, pred_dates, succ_dates):
241
        """
242
        Edges from a dual Gx_node in the mapping should be ordered in
243
        a time-respecting manner.
244
        """
245
        time_respecting = True
246
        pred_dates.sort()
247
        succ_dates.sort()
248
        # First out before last in; negative of the necessary condition for time-respect.
249
        if 0 < len(succ_dates) and 0 < len(pred_dates) and succ_dates[0] < pred_dates[-1]:
250
            time_respecting = False
251
        return time_respecting
252

    
253
    def semantic_feasibility(self, G1_node, G2_node):
254
        """Returns True if adding (G1_node, G2_node) is semantically
255
        feasible.
256

257
        Any subclass which redefines semantic_feasibility() must
258
        maintain the self.tests if needed, to keep the match() method
259
        functional. Implementations should consider multigraphs.
260
        """
261
        pred, succ = [n for n in self.G1.predecessors(G1_node) if n in self.core_1], [
262
            n for n in self.G1.successors(G1_node) if n in self.core_1]
263
        if not self.one_hop(self.G1, G1_node, self.core_1, pred, succ):  # Fail fast on first node.
264
            return False
265
        if not self.two_hop_pred(self.G1, G1_node, self.core_1, pred):
266
            return False
267
        if not self.two_hop_succ(self.G1, G1_node, self.core_1, succ):
268
            return False
269
        # Otherwise, this node is semantically feasible!
270
        return True