SNAP Library 4.1, Developer Reference  2018-07-26 16:30:42
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
temporalmotifs.h
Go to the documentation of this file.
1 #ifndef snap_temporalmotifs_h
2 #define snap_temporalmotifs_h
3 
4 #include "Snap.h"
5 
7 
8 // Simple one-dimensional, two-dimensional, and three-dimensional counter
9 // classes with default intialization.
10 class Counter1D {
11  public:
12  Counter1D(int m=0) : m_(m) {
13  if (m > 0) {
14  data_ = TUInt64V(m);
15  data_.PutAll(0);
16  }
17  }
18  const TUInt64& operator()(int i) const { return data_[i]; }
19  TUInt64& operator()(int i) { return data_[i]; }
20  int m() { return m_; }
21 
22  private:
23  int m_;
25 };
26 
27 class Counter2D {
28  public:
29  Counter2D(int m=0, int n=0) : m_(m), n_(n) {
30  if (m * n > 0) {
31  data_ = TUInt64V(m * n);
32  data_.PutAll(0);
33  }
34  }
35  const TUInt64& operator()(int i, int j) const { return data_[i + j * m_]; }
36  TUInt64& operator()(int i, int j) { return data_[i + j * m_]; }
37  int m() { return m_; }
38  int n() { return n_; }
39 
40  private:
41  int m_;
42  int n_;
44 };
45 
46 class Counter3D {
47  public:
48  Counter3D(int m=0, int n=0, int p=0) : m_(m), n_(n), p_(p) {
49  if (m * n * p > 0) {
50  data_ = TUInt64V(m * n * p);
51  data_.PutAll(0);
52  }
53  }
54  const TUInt64& operator()(int i, int j, int k) const {
55  return data_[i + j * n_ + k * m_ * n_];
56  }
57  TUInt64& operator()(int i, int j, int k) {
58  return data_[i + j * m_ + k * m_ * n_];
59  }
60  int m() { return m_; }
61  int n() { return n_; }
62  int p() { return p_; }
63 
64  private:
65  int m_;
66  int n_;
67  int p_;
69 };
70 
71 // Triad edge data consists of a neighbor, a direction, and an indicator of whether
72 // the edge connects with wich endpoint (u or v).
74  public:
76  TriadEdgeData(int _nbr, int _dir, int _u_or_v) :
77  nbr(_nbr), dir(_dir), u_or_v(_u_or_v) {}
78  int nbr; // Which neighbor of the center node
79  int dir; // Outgoing (0) or incoming (1) direction
80  int u_or_v; // Points to first end point u (0) or second end point v (1)
81 };
82 
83 // Star edge data consists of a neighbor and a direction.
84 class StarEdgeData {
85  public:
87  StarEdgeData(int _nbr, int _dir) : nbr(_nbr), dir(_dir) {}
88  int nbr; // Which neighbor of the center node
89  int dir; // Outgoing (0) or incoming (1) direction
90 };
91 
92 // Main temporal motif counting class. This implementation has support for
93 // counting motifs with three temporal edges on two or three nodes.
95  public:
96  // Reads directed temporal graph data from the specified file, which must have
97  // the following format:
98  // source_node destination_node unix_timestamp
99  TempMotifCounter(const TStr& filename);
100 
101  // Count all three temporal edge, two-node delta-temporal motifs and fills the
102  // counter counts with the results. The format is:
103  // counts(0, 0): u --> v, v --> u, u --> v (M_{5,1})
104  // counts(0, 1): u --> v, v --> u, v --> u (M_{5,2})
105  // counts(1, 0): u --> v, u --> v, u --> v (M_{6,1})
106  // counts(1, 1): u --> v, u --> v, v --> u (M_{6,2})
107  void Count3TEdge2Node(double delta, Counter2D& counts);
108 
109  // Similar to Count3TEdge2Node() except only counts motif instances
110  // for a given pair of nodes u and v and specifies the source and destination
111  // node. The counts format is:
112  // counts(0, 0, 0): u --> v, u --> v, u --> v
113  // counts(1, 1, 1): v --> u, v --> u, v --> u
114  // counts(0, 1, 1): u --> v, v --> u, v --> u
115  // counts(1, 0, 0): v --> u, u --> v, u --> v
116  // counts(0, 1, 0): u --> v, v --> u, u --> v
117  // counts(1, 0, 1): v --> u, u --> v, v --> u
118  // counts(0, 0, 1): u --> v, u --> v, v --> u
119  // counts(1, 1, 0): v --> u, v --> u, u --> v
120  void Count3TEdge2Node(int u, int v, double delta, Counter3D& counts);
121 
122  // Counts 3-edge, 3-node star motifs and places the results in pre_counts,
123  // pos_counts, and mid_counts. Counts take the following structure (with
124  // center node c):
125  //
126  // pre: {c, u}, {c, u}, {c, v}
127  // pos: {c, u}, {c, v}, {c, v}
128  // mid: {c, u}, {c, v}, {c, u}
129  //
130  // The indicies in the counter correspond to the direction with the center
131  // node as the reference (0 indexes outgoing and 1 indexes incoming edges to
132  // the center). For example,
133  //
134  // pos_counts(0, 1, 0): c --> u, v --> c, c --> v
135  void Count3TEdge3NodeStars(double delta, Counter3D& pre_counts,
136  Counter3D& pos_counts, Counter3D& mid_counts);
137 
138  // Counts the same information as Count3TEdge3NodeStars() but uses a naive
139  // counting algorithm that iterates over all pairs of neighbors.
140  void Count3TEdge3NodeStarsNaive(double delta, Counter3D& pre_counts,
141  Counter3D& pos_counts, Counter3D& mid_counts);
142 
143  // Counts 3-edge triad events and places the result in counts:
144  //
145  // counts(0, 0, 0): u --> v, w --> v, u --> w (M_{1,3})
146  // counts(0, 0, 1): u --> v, w --> v, w --> u (M_{1,4})
147  // counts(0, 1, 0): u --> v, v --> w, u --> w (M_{2,3})
148  // counts(0, 1, 1): u --> v, v --> w, w --> u (M_{2,4})
149  // counts(1, 0, 0): u --> v, w --> u, v --> w (M_{3,5})
150  // counts(1, 0, 1): u --> v, w --> u, w --> v (M_{3,6})
151  // counts(1, 1, 0): u --> v, u --> w, v --> w (M_{4,5})
152  // counts(1, 1, 1): u --> v, u --> w, w --> v (M_{4,6})
153  void Count3TEdgeTriads(double delta, Counter3D& counts);
154 
155  // Counts the same information as Count3TEdgeTriads() but uses a naive
156  // counting algorithm that enumerates over all triangles in the static graph.
157  void Count3TEdgeTriadsNaive(double delta, Counter3D& counts);
158 
159  // Counts all 3-edge, {2,3}-node temporal motifs and places the result in
160  // counts such that counts(i, j) corresponds to motif M_{i,j}.
161  void Count3TEdge23Node(double delta, Counter2D& counts);
162 
163  private:
164  // Get all triangles in the static graph, (Us(i), Vs(i), Ws(i)) is the ith
165  // triangle.
166  void GetAllStaticTriangles(TIntV& Us, TIntV& Vs, TIntV& Ws);
167  // Fills nbrs with all neighbors (ignoring direction) of the node in the
168  // static graph.
169  void GetAllNeighbors(int node, TIntV& nbrs);
170  // Fills nodes with a vector of all nodes in the static graph.
171  void GetAllNodes(TIntV& nodes);
172 
173  // Checks whether or not there is a temporal edge along the static edge (u, v)
174  bool HasEdges(int u, int v);
175 
176  // A simple wrapper for adding triad edge data
177  void AddTriadEdgeData(TVec<TriadEdgeData>& events, TVec<TIntPair>& ts_indices,
178  int& index, int u, int v, int nbr, int key1, int key2);
179  // A simple wrapper for adding star edge data
180  void AddStarEdgeData(TVec<TIntPair>& ts_indices, TVec<StarEdgeData>& events,
181  int& index, int u, int v, int nbr, int key);
182  // Another simple wrapper for adding star edge data
183  void AddStarEdges(TVec<TIntPair>& combined, int u, int v, int key);
184 
185  // Directed graph from ignoring timestamps
187 
188  // Core data structure for storing temporal edges. temporal_data_[u](v) is a
189  // list of temporal edges along the static edge (u, v).
191 };
192 
193 // This class exhaustively counts all size^3 three-edge temporal motifs in an
194 // alphabet of a given size.
196  public:
197  // Initialize counter with a given alphabet size
198  ThreeTEdgeMotifCounter(int size) : size_(size) {}
199 
200  // Count all three-edge motifs with corresponding timestamps. Each integer in
201  // the event_string must belong to the set {0, 1, ..., size - 1}. The function
202  // stores the results in the counter, where counts(e, f, g) is the motif consisting
203  // of the ordered edges e, f, g.
204  void Count(const TIntV& event_string, const TIntV& timestamps,
205  double delta, Counter3D& counts);
206 
207  private:
208  void IncrementCounts(int event);
209  void DecrementCounts(int event);
213  int size_; // alphabet size
214 };
215 
216 // Base class for 3-edge, 3-node star and triangle counters. The template type
217 // describes the data needed when processing an edge.
218 template <typename EdgeData>
220  public:
222  void Count(const TVec<EdgeData>& events, const TIntV& timestamps, double delta);
223 
224  protected:
225  // These methods depend on the motif type (star or triad).
226  virtual void InitializeCounters() = 0;
227  virtual void PopPre(const EdgeData& event) = 0;
228  virtual void PopPos(const EdgeData& event) = 0;
229  virtual void PushPre(const EdgeData& event) = 0;
230  virtual void PushPos(const EdgeData& event) = 0;
231  virtual void ProcessCurrent(const EdgeData& event) = 0;
232 };
233 
234 // Class for counting star motifs with a given center node.
235 class ThreeTEdgeStarCounter : public StarTriad3TEdgeCounter<StarEdgeData> {
236  public:
237  // Construct class with maximum number of neighbor nodes. Each processed edge
238  // consists of a neighbor and a direction where the neighbor is represented by
239  // an int belong to the set {0, 1, ..., max_nodes - 1}.
240  ThreeTEdgeStarCounter(int max_nodes) : max_nodes_(max_nodes) {}
241 
242  // Counting conventions follow TempMotifCounter::Count3TEdge3NodeStars().
243  int PreCount(int dir1, int dir2, int dir3) { return pre_counts_(dir1, dir2, dir3); }
244  int PosCount(int dir1, int dir2, int dir3) { return pos_counts_(dir1, dir2, dir3); }
245  int MidCount(int dir1, int dir2, int dir3) { return mid_counts_(dir1, dir2, dir3); }
246 
247  protected:
248  void InitializeCounters();
249  void PopPre(const StarEdgeData& event);
250  void PopPos(const StarEdgeData& event);
251  void PushPre(const StarEdgeData& event);
252  void PushPos(const StarEdgeData& event);
253  void ProcessCurrent(const StarEdgeData& event);
254 
255  private:
265 };
266 
267 
268 // Class for counting triangle motifs that contain a specific undirected edge.
269 class ThreeTEdgeTriadCounter : public StarTriad3TEdgeCounter<TriadEdgeData> {
270  public:
271  // Construct class with maximum number of neighbor nodes. Each processed edge
272  // consists of a neighbor, a direction, and an indicator of which end point it
273  // connects with. Each neighbor is represented by an int belong to the set
274  // {0, 1, ..., max_nodes - 1}.
275  ThreeTEdgeTriadCounter(int max_nodes, int node_u, int node_v) :
276  max_nodes_(max_nodes), node_u_(node_u), node_v_(node_v) {}
277 
278  // Counting conventions follow TempMotifCounter::Count3TEdgeTriads().
279  int Counts(int dir1, int dir2, int dir3) { return triad_counts_(dir1, dir2, dir3); }
280 
281  protected:
282  void InitializeCounters();
283  void PopPre(const TriadEdgeData& event);
284  void PopPos(const TriadEdgeData& event);
285  void PushPre(const TriadEdgeData& event);
286  void PushPos(const TriadEdgeData& event);
287  void ProcessCurrent(const TriadEdgeData& event);
288  bool IsEdgeNode(int nbr) { return nbr == node_u_ || nbr == node_v_; }
289 
290  private:
298  // Two end points of the edge whose triangles this class counts.
299  int node_u_;
300  int node_v_;
301 };
302 
303 #endif // snap_temporalmotifs_h
Definition: ds.h:346
bool HasEdges(int u, int v)
void Count(const TVec< EdgeData > &events, const TIntV &timestamps, double delta)
void GetAllNodes(TIntV &nodes)
TempMotifCounter(const TStr &filename)
int PreCount(int dir1, int dir2, int dir3)
TUInt64V data_
TKeyDat< TInt, TInt > TIntPair
Definition: temporalmotifs.h:6
void Count(const TIntV &event_string, const TIntV &timestamps, double delta, Counter3D &counts)
void Count3TEdgeTriadsNaive(double delta, Counter3D &counts)
virtual void PushPre(const EdgeData &event)=0
void ProcessCurrent(const StarEdgeData &event)
void Count3TEdge23Node(double delta, Counter2D &counts)
void PopPre(const StarEdgeData &event)
virtual void PopPre(const EdgeData &event)=0
TUInt64V data_
void PopPre(const TriadEdgeData &event)
virtual void PopPos(const EdgeData &event)=0
void PopPos(const StarEdgeData &event)
const TUInt64 & operator()(int i, int j) const
int PosCount(int dir1, int dir2, int dir3)
void PopPos(const TriadEdgeData &event)
Counter1D(int m=0)
void GetAllStaticTriangles(TIntV &Us, TIntV &Vs, TIntV &Ws)
const TUInt64 & operator()(int i) const
virtual void InitializeCounters()=0
void AddStarEdgeData(TVec< TIntPair > &ts_indices, TVec< StarEdgeData > &events, int &index, int u, int v, int nbr, int key)
void ProcessCurrent(const TriadEdgeData &event)
const TUInt64 & operator()(int i, int j, int k) const
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
virtual void ProcessCurrent(const EdgeData &event)=0
void IncrementCounts(int event)
ThreeTEdgeStarCounter(int max_nodes)
void Count3TEdge3NodeStars(double delta, Counter3D &pre_counts, Counter3D &pos_counts, Counter3D &mid_counts)
Counter2D(int m=0, int n=0)
StarEdgeData(int _nbr, int _dir)
void GetAllNeighbors(int node, TIntV &nbrs)
Counter3D(int m=0, int n=0, int p=0)
int Counts(int dir1, int dir2, int dir3)
TUInt64 & operator()(int i, int j, int k)
TriadEdgeData(int _nbr, int _dir, int _u_or_v)
void PushPos(const StarEdgeData &event)
TUInt64V data_
ThreeTEdgeMotifCounter(int size)
void AddTriadEdgeData(TVec< TriadEdgeData > &events, TVec< TIntPair > &ts_indices, int &index, int u, int v, int nbr, int key1, int key2)
void DecrementCounts(int event)
ThreeTEdgeTriadCounter(int max_nodes, int node_u, int node_v)
TVec< TUInt64 > TUInt64V
Definition: ds.h:1595
Definition: dt.h:412
virtual void PushPos(const EdgeData &event)=0
void Count3TEdge2Node(double delta, Counter2D &counts)
void PushPre(const StarEdgeData &event)
void Count3TEdgeTriads(double delta, Counter3D &counts)
void PushPre(const TriadEdgeData &event)
void AddStarEdges(TVec< TIntPair > &combined, int u, int v, int key)
int MidCount(int dir1, int dir2, int dir3)
bool IsEdgeNode(int nbr)
TUInt64 & operator()(int i, int j)
TUInt64 & operator()(int i)
TVec< THash< TInt, TIntV > > temporal_data_
void PushPos(const TriadEdgeData &event)
Definition: dt.h:1315
void Count3TEdge3NodeStarsNaive(double delta, Counter3D &pre_counts, Counter3D &pos_counts, Counter3D &mid_counts)