SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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:1318
void Count3TEdge3NodeStarsNaive(double delta, Counter3D &pre_counts, Counter3D &pos_counts, Counter3D &mid_counts)