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.cpp
Go to the documentation of this file.
1 #include "Snap.h"
2 #include "temporalmotifs.h"
3 
5 // Initialization and helper methods for TempMotifCounter
7  // First load the static graph
8  static_graph_ = TSnap::LoadEdgeList<PNGraph>(filename, 0, 1);
9  int max_nodes = static_graph_->GetMxNId();
11 
12  // Formulate input File Format:
13  // source_node destination_node timestamp
14  TTableContext context;
15  Schema temp_graph_schema;
16  temp_graph_schema.Add(TPair<TStr,TAttrType>("source", atInt));
17  temp_graph_schema.Add(TPair<TStr,TAttrType>("destination", atInt));
18  temp_graph_schema.Add(TPair<TStr,TAttrType>("time", atInt));
19 
20  // Load the temporal graph
21  PTable data_ptr = TTable::LoadSS(temp_graph_schema, filename, &context, ' ');
22  TInt src_idx = data_ptr->GetColIdx("source");
23  TInt dst_idx = data_ptr->GetColIdx("destination");
24  TInt tim_idx = data_ptr->GetColIdx("time");
25  for (TRowIterator RI = data_ptr->BegRI(); RI < data_ptr->EndRI(); RI++) {
26  TInt row_idx = RI.GetRowIdx();
27  int src = data_ptr->GetIntValAtRowIdx(src_idx, row_idx).Val;
28  int dst = data_ptr->GetIntValAtRowIdx(dst_idx, row_idx).Val;
29  int tim = data_ptr->GetIntValAtRowIdx(tim_idx, row_idx).Val;
30  // Do not include self loops as they do not appear in the definition of
31  // temporal motifs.
32  if (src != dst) { temporal_data_[src](dst).Add(tim); }
33  }
34 }
35 
37  nodes = TIntV();
38  for (TNGraph::TNodeI it = static_graph_->BegNI();
39  it < static_graph_->EndNI(); it++) {
40  nodes.Add(it.GetId());
41  }
42 }
43 
44 bool TempMotifCounter::HasEdges(int u, int v) {
45  return temporal_data_[u].IsKey(v);
46 }
47 
49  nbrs = TIntV();
51  for (int i = 0; i < NI.GetOutDeg(); i++) { nbrs.Add(NI.GetOutNId(i)); }
52  for (int i = 0; i < NI.GetInDeg(); i++) {
53  int nbr = NI.GetInNId(i);
54  if (!NI.IsOutNId(nbr)) { nbrs.Add(nbr); }
55  }
56 }
57 
59  Us.Clr();
60  Vs.Clr();
61  Ws.Clr();
62  // Get degree ordering of the graph
63  int max_nodes = static_graph_->GetMxNId();
64  TVec<TIntPair> degrees(max_nodes);
65  degrees.PutAll(TIntPair(0, 0));
66  // Set the degree of a node to be the number of nodes adjacent to the node in
67  // the undirected graph.
68  TIntV nodes;
69  GetAllNodes(nodes);
70  #pragma omp parallel for schedule(dynamic)
71  for (int node_id = 0; node_id < nodes.Len(); node_id++) {
72  int src = nodes[node_id];
73  TIntV nbrs;
74  GetAllNeighbors(src, nbrs);
75  degrees[src] = TIntPair(nbrs.Len(), src);
76  }
77  degrees.Sort();
78  TIntV order = TIntV(max_nodes);
79  #pragma omp parallel for schedule(dynamic)
80  for (int i = 0; i < order.Len(); i++) {
81  order[degrees[i].Dat] = i;
82  }
83 
84  // Get triangles centered at a given node where that node is the smallest in
85  // the degree ordering.
86  #pragma omp parallel for schedule(dynamic)
87  for (int node_id = 0; node_id < nodes.Len(); node_id++) {
88  int src = nodes[node_id];
89  int src_pos = order[src];
90 
91  // Get all neighbors who come later in the ordering
92  TIntV nbrs;
93  GetAllNeighbors(src, nbrs);
94  TIntV neighbors_higher;
95  for (int i = 0; i < nbrs.Len(); i++) {
96  int nbr = nbrs[i];
97  if (order[nbr] > src_pos) { neighbors_higher.Add(nbr); }
98  }
99 
100  for (int ind1 = 0; ind1 < neighbors_higher.Len(); ind1++) {
101  for (int ind2 = ind1 + 1; ind2 < neighbors_higher.Len(); ind2++) {
102  int dst1 = neighbors_higher[ind1];
103  int dst2 = neighbors_higher[ind2];
104  // Check for triangle formation
105  if (static_graph_->IsEdge(dst1, dst2) || static_graph_->IsEdge(dst2, dst1)) {
106  #pragma omp critical
107  {
108  Us.Add(src);
109  Vs.Add(dst1);
110  Ws.Add(dst2);
111  }
112  }
113  }
114  }
115  }
116 }
117 
118 void TempMotifCounter::Count3TEdge23Node(double delta, Counter2D& counts) {
119  // This is imply a wrapper function around the counting methods to produce
120  // counts in the same way that they were represented in the paper. This makes
121  // it easy to reproduce results and allow SNAP users to make the same
122  // measurements on their temporal network data.
123  counts = Counter2D(6, 6);
124 
125  Counter2D edge_counts;
126  Count3TEdge2Node(delta, edge_counts);
127  counts(4, 0) = edge_counts(0, 0);
128  counts(4, 1) = edge_counts(0, 1);
129  counts(5, 0) = edge_counts(1, 0);
130  counts(5, 1) = edge_counts(1, 1);
131 
132  Counter3D pre_counts, pos_counts, mid_counts;
133  Count3TEdge3NodeStars(delta, pre_counts, pos_counts, mid_counts);
134  counts(0, 0) = mid_counts(1, 1, 1);
135  counts(0, 1) = mid_counts(1, 1, 0);
136  counts(0, 4) = pos_counts(1, 1, 0);
137  counts(0, 5) = pos_counts(1, 1, 1);
138  counts(1, 0) = mid_counts(1, 0, 1);
139  counts(1, 1) = mid_counts(1, 0, 0);
140  counts(1, 4) = pos_counts(1, 0, 0);
141  counts(1, 5) = pos_counts(1, 0, 1);
142  counts(2, 0) = mid_counts(0, 1, 0);
143  counts(2, 1) = mid_counts(0, 1, 1);
144  counts(2, 2) = pos_counts(0, 1, 0);
145  counts(2, 3) = pos_counts(0, 1, 1);
146  counts(3, 0) = mid_counts(0, 0, 0);
147  counts(3, 1) = mid_counts(0, 0, 1);
148  counts(3, 2) = pos_counts(0, 0, 0);
149  counts(3, 3) = pos_counts(0, 0, 1);
150  counts(4, 2) = pre_counts(0, 1, 0);
151  counts(4, 3) = pre_counts(0, 1, 1);
152  counts(4, 4) = pre_counts(1, 0, 0);
153  counts(4, 5) = pre_counts(1, 0, 1);
154  counts(5, 2) = pre_counts(0, 0, 0);
155  counts(5, 3) = pre_counts(0, 0, 1);
156  counts(5, 4) = pre_counts(1, 1, 0);
157  counts(5, 5) = pre_counts(1, 1, 1);
158 
159  Counter3D triad_counts;
160  Count3TEdgeTriads(delta, triad_counts);
161  counts(0, 2) = triad_counts(0, 0, 0);
162  counts(0, 3) = triad_counts(0, 0, 1);
163  counts(1, 2) = triad_counts(0, 1, 0);
164  counts(1, 3) = triad_counts(0, 1, 1);
165  counts(2, 4) = triad_counts(1, 0, 0);
166  counts(2, 5) = triad_counts(1, 0, 1);
167  counts(3, 4) = triad_counts(1, 1, 0);
168  counts(3, 5) = triad_counts(1, 1, 1);
169 }
170 
172 // Two-node (static edge) counting methods
173 void TempMotifCounter::Count3TEdge2Node(double delta, Counter2D& counts) {
174  // Get a vector of undirected edges (so we can use openmp parallel for over it)
175  TVec<TIntPair> undir_edges;
176  for (TNGraph::TEdgeI it = static_graph_->BegEI(); it < static_graph_->EndEI(); it++) {
177  int src = it.GetSrcNId();
178  int dst = it.GetDstNId();
179  // Only consider undirected edges
180  if (src < dst || (dst < src && !static_graph_->IsEdge(dst, src))) {
181  undir_edges.Add(TIntPair(src, dst));
182  }
183  }
184  counts = Counter2D(2, 2);
185  #pragma omp parallel for schedule(dynamic)
186  for (int i = 0; i < undir_edges.Len(); i++) {
187  TIntPair edge = undir_edges[i];
188  Counter3D local;
189  Count3TEdge2Node(edge.Key, edge.Dat, delta, local);
190  #pragma omp critical
191  {
192  counts(0, 0) += local(0, 1, 0) + local(1, 0, 1); // M_{5,1}
193  counts(0, 1) += local(1, 0, 0) + local(0, 1, 1); // M_{5,2}
194  counts(1, 0) += local(0, 0, 0) + local(1, 1, 1); // M_{6,1}
195  counts(1, 1) += local(0, 0, 1) + local(1, 1, 0); // M_{6,2}
196  }
197  }
198 }
199 
200 void TempMotifCounter::Count3TEdge2Node(int u, int v, double delta,
201  Counter3D& counts) {
202  // Sort event list by time
203  TVec<TIntPair> combined;
204  AddStarEdges(combined, u, v, 0);
205  AddStarEdges(combined, v, u, 1);
206  combined.Sort();
207 
208  // Get the counts
209  ThreeTEdgeMotifCounter counter(2);
210  TIntV in_out(combined.Len());
211  TIntV timestamps(combined.Len());
212  for (int k = 0; k < combined.Len(); k++) {
213  in_out[k] = combined[k].Dat;
214  timestamps[k] = combined[k].Key;
215  }
216  counter.Count(in_out, timestamps, delta, counts);
217 }
218 
220 // Star counting methods
221 void TempMotifCounter::AddStarEdges(TVec<TIntPair>& combined, int u, int v,
222  int key) {
223  if (HasEdges(u, v)) {
224  const TIntV& timestamps = temporal_data_[u].GetDat(v);
225  for (int i = 0; i < timestamps.Len(); i++) {
226  combined.Add(TIntPair(timestamps[i], key));
227  }
228  }
229 }
230 
232  double delta, Counter3D& pre_counts, Counter3D& pos_counts,
233  Counter3D& mid_counts) {
234  TIntV centers;
235  GetAllNodes(centers);
236  pre_counts = Counter3D(2, 2, 2);
237  pos_counts = Counter3D(2, 2, 2);
238  mid_counts = Counter3D(2, 2, 2);
239  // Get counts for each node as the center
240  #pragma omp parallel for schedule(dynamic)
241  for (int c = 0; c < centers.Len(); c++) {
242  // Gather all adjacent events
243  int center = centers[c];
244  TIntV nbrs;
245  GetAllNeighbors(center, nbrs);
246  for (int i = 0; i < nbrs.Len(); i++) {
247  for (int j = i + 1; j < nbrs.Len(); j++) {
248  int nbr1 = nbrs[i];
249  int nbr2 = nbrs[j];
250  TVec<TIntPair> combined;
251  AddStarEdges(combined, center, nbr1, 0);
252  AddStarEdges(combined, nbr1, center, 1);
253  AddStarEdges(combined, center, nbr2, 2);
254  AddStarEdges(combined, nbr2, center, 3);
255  combined.Sort();
256  ThreeTEdgeMotifCounter counter(4);
257  TIntV edge_id(combined.Len());
258  TIntV timestamps(combined.Len());
259  for (int k = 0; k < combined.Len(); k++) {
260  edge_id[k] = combined[k].Dat;
261  timestamps[k] = combined[k].Key;
262  }
263  Counter3D local;
264  counter.Count(edge_id, timestamps, delta, local);
265 
266  #pragma omp critical
267  { // Update with local counts
268  for (int dir1 = 0; dir1 < 2; ++dir1) {
269  for (int dir2 = 0; dir2 < 2; ++dir2) {
270  for (int dir3 = 0; dir3 < 2; ++dir3) {
271  pre_counts(dir1, dir2, dir3) +=
272  local(dir1, dir2, dir3 + 2) + local(dir1 + 2, dir2 + 2, dir3);
273  pos_counts(dir1, dir2, dir3) +=
274  local(dir1, dir2 + 2, dir3 + 2) + local(dir1 + 2, dir2, dir3);
275  mid_counts(dir1, dir2, dir3) +=
276  local(dir1, dir2 + 2, dir3) + local(dir1 + 2, dir2, dir3 + 2);
277  }
278  }
279  }
280  }
281  }
282  }
283  }
284 }
285 
287  TVec<StarEdgeData>& events,
288  int& index, int u, int v, int nbr, int key) {
289  if (HasEdges(u, v)) {
290  const TIntV& ts_vec = temporal_data_[u].GetDat(v);
291  for (int j = 0; j < ts_vec.Len(); ++j) {
292  ts_indices.Add(TIntPair(ts_vec[j], index));
293  events.Add(StarEdgeData(nbr, key));
294  index++;
295  }
296  }
297 }
298 
299 void TempMotifCounter::Count3TEdge3NodeStars(double delta, Counter3D& pre_counts,
300  Counter3D& pos_counts,
301  Counter3D& mid_counts) {
302  TIntV centers;
303  GetAllNodes(centers);
304  pre_counts = Counter3D(2, 2, 2);
305  pos_counts = Counter3D(2, 2, 2);
306  mid_counts = Counter3D(2, 2, 2);
307  // Get counts for each node as the center
308  #pragma omp parallel for schedule(dynamic)
309  for (int c = 0; c < centers.Len(); c++) {
310  // Gather all adjacent events
311  int center = centers[c];
312  TVec<TIntPair> ts_indices;
313  TVec<StarEdgeData> events;
314  TNGraph::TNodeI NI = static_graph_->GetNI(center);
315  int index = 0;
316  TIntV nbrs;
317  GetAllNeighbors(center, nbrs);
318  int nbr_index = 0;
319  for (int i = 0; i < nbrs.Len(); i++) {
320  int nbr = nbrs[i];
321  AddStarEdgeData(ts_indices, events, index, center, nbr, nbr_index, 0);
322  AddStarEdgeData(ts_indices, events, index, nbr, center, nbr_index, 1);
323  nbr_index++;
324  }
325  ts_indices.Sort();
326  TIntV timestamps;
327  TVec<StarEdgeData> ordered_events;
328  for (int j = 0; j < ts_indices.Len(); j++) {
329  timestamps.Add(ts_indices[j].Key);
330  ordered_events.Add(events[ts_indices[j].Dat]);
331  }
332 
333  ThreeTEdgeStarCounter tesc(nbr_index);
334  // dirs: outgoing --> 0, incoming --> 1
335  tesc.Count(ordered_events, timestamps, delta);
336  #pragma omp critical
337  { // Update counts
338  for (int dir1 = 0; dir1 < 2; ++dir1) {
339  for (int dir2 = 0; dir2 < 2; ++dir2) {
340  for (int dir3 = 0; dir3 < 2; ++dir3) {
341  pre_counts(dir1, dir2, dir3) += tesc.PreCount(dir1, dir2, dir3);
342  pos_counts(dir1, dir2, dir3) += tesc.PosCount(dir1, dir2, dir3);
343  mid_counts(dir1, dir2, dir3) += tesc.MidCount(dir1, dir2, dir3);
344  }
345  }
346  }
347  }
348 
349  // Subtract off edge-wise counts
350  for (int nbr_id = 0; nbr_id < nbrs.Len(); nbr_id++) {
351  int nbr = nbrs[nbr_id];
352  Counter3D edge_counts;
353  Count3TEdge2Node(center, nbr, delta, edge_counts);
354  #pragma omp critical
355  {
356  for (int dir1 = 0; dir1 < 2; ++dir1) {
357  for (int dir2 = 0; dir2 < 2; ++dir2) {
358  for (int dir3 = 0; dir3 < 2; ++dir3) {
359  pre_counts(dir1, dir2, dir3) -= edge_counts(dir1, dir2, dir3);
360  pos_counts(dir1, dir2, dir3) -= edge_counts(dir1, dir2, dir3);
361  mid_counts(dir1, dir2, dir3) -= edge_counts(dir1, dir2, dir3);
362  }
363  }
364  }
365  }
366  }
367  }
368 }
369 
371 // Triad counting methods
373  TIntV Us, Vs, Ws;
374  GetAllStaticTriangles(Us, Vs, Ws);
375  counts = Counter3D(2, 2, 2);
376  #pragma omp parallel for schedule(dynamic)
377  for (int i = 0; i < Us.Len(); i++) {
378  int u = Us[i];
379  int v = Vs[i];
380  int w = Ws[i];
381  // Gather all edges in triangle (u, v, w)
382  int uv = 0, vu = 1, uw = 2, wu = 3, vw = 4, wv = 5;
383  TVec<TIntPair> combined;
384  AddStarEdges(combined, u, v, uv);
385  AddStarEdges(combined, v, u, vu);
386  AddStarEdges(combined, u, w, uw);
387  AddStarEdges(combined, w, u, wu);
388  AddStarEdges(combined, v, w, vw);
389  AddStarEdges(combined, w, v, wv);
390  // Get the counts for this triangle
391  combined.Sort();
392  ThreeTEdgeMotifCounter counter(6);
393  TIntV edge_id(combined.Len());
394  TIntV timestamps(combined.Len());
395  for (int k = 0; k < combined.Len(); k++) {
396  edge_id[k] = combined[k].Dat;
397  timestamps[k] = combined[k].Key;
398  }
399  Counter3D local;
400  counter.Count(edge_id, timestamps, delta, local);
401 
402  // Update the global counter with the various symmetries
403  #pragma omp critical
404  {
405  // i --> j, k --> j, i --> k
406  counts(0, 0, 0) += local(uv, wv, uw) + local(vu, wu, vw) + local(uw, vw, uv)
407  + local(wu, vu, wv) + local(vw, uw, vu) + local(wv, uv, wu);
408  // i --> j, k --> j, k --> i
409  counts(0, 0, 1) += local(uv, wv, wu) + local(vu, wu, wv) + local(uw, vw, vu)
410  + local(wu, vu, vw) + local(vw, uw, uv) + local(wv, uv, uw);
411  // i --> j, j --> k, i --> k
412  counts(0, 1, 0) += local(uv, vw, uw) + local(vu, uw, vw) + local(uw, wv, uv)
413  + local(wu, uv, wv) + local(vw, wu, vu) + local(wv, vu, wu);
414  // i --> j, j --> k, k --> i
415  counts(0, 1, 1) += local(uv, vw, wu) + local(vu, uw, wv) + local(uw, wv, vu)
416  + local(wu, uv, vw) + local(vw, wu, uv) + local(wv, vu, uw);
417  // i --> j, k --> i, j --> k
418  counts(1, 0, 0) += local(uv, wu, vw) + local(vu, wv, uw) + local(uw, vu, wv)
419  + local(wu, vw, uv) + local(vw, uv, wu) + local(wv, uw, vu);
420  // i --> j, k --> i, k --> j
421  counts(1, 0, 1) += local(uv, wu, wv) + local(vu, wv, wu) + local(uw, vu, vw)
422  + local(wu, vw, vu) + local(vw, uv, uw) + local(wv, uw, uv);
423  // i --> j, i --> k, j --> k
424  counts(1, 1, 0) += local(uv, uw, vw) + local(vu, vw, uw) + local(uw, uv, wv)
425  + local(wu, wv, uv) + local(vw, vu, wu) + local(wv, wu, vu);
426  // i --> j, i --> k, k --> j
427  counts(1, 1, 1) += local(uv, uw, wv) + local(vu, vw, wu) + local(uw, uv, vw)
428  + local(wu, wv, vu) + local(vw, vu, uw) + local(wv, wu, uv);
429  }
430  }
431 }
432 
434  TVec<TIntPair>& ts_indices,
435  int& index, int u, int v, int nbr,
436  int key1, int key2) {
437  if (HasEdges(u, v)) {
438  const TIntV& timestamps = temporal_data_[u].GetDat(v);
439  for (int i = 0; i < timestamps.Len(); i++) {
440  ts_indices.Add(TIntPair(timestamps[i], index));
441  events.Add(TriadEdgeData(nbr, key1, key2));
442  ++index;
443  }
444  }
445 }
446 
447 void TempMotifCounter::Count3TEdgeTriads(double delta, Counter3D& counts) {
448  counts = Counter3D(2, 2, 2);
449 
450  // Get the counts on each undirected edge
453  for (TNGraph::TEdgeI it = static_graph_->BegEI();
454  it < static_graph_->EndEI(); it++) {
455  int src = it.GetSrcNId();
456  int dst = it.GetDstNId();
457  int min_node = MIN(src, dst);
458  int max_node = MAX(src, dst);
459  edge_counts[min_node](max_node) += temporal_data_[src](dst).Len();
460  assignments[min_node](max_node) = TIntV();
461  }
462 
463  // Assign triangles to the edge with the most events
464  TIntV Us, Vs, Ws;
465  GetAllStaticTriangles(Us, Vs, Ws);
466  #pragma omp parallel for schedule(dynamic)
467  for (int i = 0; i < Us.Len(); i++) {
468  int u = Us[i];
469  int v = Vs[i];
470  int w = Ws[i];
471  int counts_uv = edge_counts[MIN(u, v)].GetDat(MAX(u, v));
472  int counts_uw = edge_counts[MIN(u, w)].GetDat(MAX(u, w));
473  int counts_vw = edge_counts[MIN(v, w)].GetDat(MAX(v, w));
474  if (counts_uv >= MAX(counts_uw, counts_vw)) {
475  #pragma omp critical
476  {
477  TIntV& assignment = assignments[MIN(u, v)].GetDat(MAX(u, v));
478  assignment.Add(w);
479  }
480  } else if (counts_uw >= MAX(counts_uv, counts_vw)) {
481  #pragma omp critical
482  {
483  TIntV& assignment = assignments[MIN(u, w)].GetDat(MAX(u, w));
484  assignment.Add(v);
485  }
486  } else if (counts_vw >= MAX(counts_uv, counts_uw)) {
487  #pragma omp critical
488  {
489  TIntV& assignment = assignments[MIN(v, w)].GetDat(MAX(v, w));
490  assignment.Add(u);
491  }
492  }
493  }
494 
495  TVec<TIntPair> all_edges;
496  TIntV all_nodes;
497  GetAllNodes(all_nodes);
498  for (int node_id = 0; node_id < all_nodes.Len(); node_id++) {
499  int u = all_nodes[node_id];
500  TIntV nbrs;
501  GetAllNeighbors(u, nbrs);
502  for (int nbr_id = 0; nbr_id < nbrs.Len(); nbr_id++) {
503  int v = nbrs[nbr_id];
504  if (assignments[u].IsKey(v) && assignments[u].GetDat(v).Len() > 0) {
505  all_edges.Add(TIntPair(u, v));
506  }
507  }
508  }
509 
510  // Count triangles on edges with the assigned neighbors
511  #pragma omp parallel for schedule(dynamic)
512  for (int edge_id = 0; edge_id < all_edges.Len(); edge_id++) {
513  TIntPair edge = all_edges[edge_id];
514  int u = edge.Key;
515  int v = edge.Dat;
516  // Continue if no assignment
517  if (!assignments[u].IsKey(v)) { continue; }
518  TIntV& uv_assignment = assignments[u].GetDat(v);
519  // Continue if no data
520  if (uv_assignment.Len() == 0) { continue; }
521  // Get all events on (u, v)
522  TVec<TriadEdgeData> events;
523  TVec<TIntPair> ts_indices;
524  int index = 0;
525  int nbr_index = 0;
526  // Assign indices from 0, 1, ..., num_nbrs + 2
527  AddTriadEdgeData(events, ts_indices, index, u, v, nbr_index, 0, 1);
528  nbr_index++;
529  AddTriadEdgeData(events, ts_indices, index, v, u, nbr_index, 0, 0);
530  nbr_index++;
531  // Get all events on triangles assigned to (u, v)
532  for (int w_id = 0; w_id < uv_assignment.Len(); w_id++) {
533  int w = uv_assignment[w_id];
534  AddTriadEdgeData(events, ts_indices, index, w, u, nbr_index, 0, 0);
535  AddTriadEdgeData(events, ts_indices, index, w, v, nbr_index, 0, 1);
536  AddTriadEdgeData(events, ts_indices, index, u, w, nbr_index, 1, 0);
537  AddTriadEdgeData(events, ts_indices, index, v, w, nbr_index, 1, 1);
538  nbr_index++;
539  }
540  // Put events in sorted order
541  ts_indices.Sort();
542  TIntV timestamps(ts_indices.Len());
543  TVec<TriadEdgeData> sorted_events(ts_indices.Len());
544  for (int i = 0; i < ts_indices.Len(); i++) {
545  timestamps[i] = ts_indices[i].Key;
546  sorted_events[i] = events[ts_indices[i].Dat];
547  }
548 
549  // Get the counts and update the counter
550  ThreeTEdgeTriadCounter tetc(nbr_index, 0, 1);
551  tetc.Count(sorted_events, timestamps, delta);
552  #pragma omp critical
553  {
554  for (int dir1 = 0; dir1 < 2; dir1++) {
555  for (int dir2 = 0; dir2 < 2; dir2++) {
556  for (int dir3 = 0; dir3 < 2; dir3++) {
557  counts(dir1, dir2, dir3) += tetc.Counts(dir1, dir2, dir3);
558  }
559  }
560  }
561  }
562  }
563 }
564 
566 // Generic three temporal edge motif counter
567 void ThreeTEdgeMotifCounter::Count(const TIntV& event_string, const TIntV& timestamps,
568  double delta, Counter3D& counts) {
569  // Initialize everything to empty
573  if (event_string.Len() != timestamps.Len()) {
574  TExcept::Throw("Number of events must equal number of timestamps");
575  }
576  int start = 0;
577  for (int end = 0; end < event_string.Len(); end++) {
578  while (double(timestamps[start]) + delta < double(timestamps[end])) {
579  DecrementCounts(event_string[start]);
580  start++;
581  }
582  IncrementCounts(event_string[end]);
583  }
584  counts = counts3_;
585 }
586 
588  for (int i = 0; i < size_; i++) {
589  for (int j = 0; j < size_; j++) {
590  counts3_(i, j, event) += counts2_(i, j);
591  }
592  }
593  for (int i = 0; i < size_; i++) { counts2_(i, event) += counts1_(i); }
594  counts1_(event) += 1;
595 }
596 
598  counts1_(event)--;
599  for (int i = 0; i < size_; i++) { counts2_(event, i) -= counts1_(i); }
600 }
601 
603 // Generic three temporal edge, three node star and triad counter.
604 template <typename EdgeData>
606  const TIntV& timestamps, double delta) {
607  InitializeCounters();
608  if (events.Len() != timestamps.Len()) {
609  TExcept::Throw("Number of events must match number of timestamps.");
610  }
611  int start = 0;
612  int end = 0;
613  int L = timestamps.Len();
614  for (int j = 0; j < L; j++) {
615  double tj = double(timestamps[j]);
616  // Adjust counts in pre-window [tj - delta, tj)
617  while (start < L && double(timestamps[start]) < tj - delta) {
618  PopPre(events[start]);
619  start++;
620  }
621  // Adjust counts in post-window (tj, tj + delta]
622  while (end < L && double(timestamps[end]) <= tj + delta) {
623  PushPos(events[end]);
624  end++;
625  }
626  // Move current event off post-window
627  PopPos(events[j]);
628  ProcessCurrent(events[j]);
629  PushPre(events[j]);
630  }
631 }
632 
634 // Methods for the main sub-routine in the fast star counting algorithm.
636  pre_sum_ = Counter2D(2, 2);
637  pos_sum_ = Counter2D(2, 2);
638  mid_sum_ = Counter2D(2, 2);
639  pre_counts_ = Counter3D(2, 2, 2);
640  pos_counts_ = Counter3D(2, 2, 2);
641  mid_counts_ = Counter3D(2, 2, 2);
644 }
645 
647  int nbr = event.nbr;
648  int dir = event.dir;
649  pre_nodes_(dir, nbr) -= 1;
650  for (int i = 0; i < 2; i++) { pre_sum_(dir, i) -= pre_nodes_(i, nbr); }
651 }
652 
654  int nbr = event.nbr;
655  int dir = event.dir;
656  pos_nodes_(dir, nbr) -= 1;
657  for (int i = 0; i < 2; i++) { pos_sum_(dir, i) -= pos_nodes_(i, nbr); }
658 }
659 
661  int nbr = event.nbr;
662  int dir = event.dir;
663  for (int i = 0; i < 2; i++) { pre_sum_(i, dir) += pre_nodes_(i, nbr); }
664  pre_nodes_(dir, nbr) += 1;
665 }
666 
668  int nbr = event.nbr;
669  int dir = event.dir;
670  for (int i = 0; i < 2; i++) { pos_sum_(i, dir) += pos_nodes_(i, nbr); }
671  pos_nodes_(dir, nbr) += 1;
672 }
673 
675  int nbr = event.nbr;
676  int dir = event.dir;
677  // Decrement middle sum
678  for (int i = 0; i < 2; i++) { mid_sum_(i, dir) -= pre_nodes_(i, nbr); }
679  // Update counts
680  for (int i = 0; i < 2; i++) {
681  for (int j = 0; j < 2; j++) {
682  pre_counts_(i, j, dir) += pre_sum_(i, j);
683  pos_counts_(dir, i, j) += pos_sum_(i, j);
684  mid_counts_(i, dir, j) += mid_sum_(i, j);
685  }
686  }
687  // Increment middle sum
688  for (int i = 0; i < 2; i++) { mid_sum_(dir, i) += pos_nodes_(i, nbr); }
689 }
690 
692 // Methods for the main sub-routine in the fast triangle counting algorithm.
696  pre_sum_ = Counter3D(2, 2, 2);
697  pos_sum_ = Counter3D(2, 2, 2);
698  mid_sum_ = Counter3D(2, 2, 2);
699  triad_counts_ = Counter3D(2, 2, 2);
700 }
701 
703  int nbr = event.nbr;
704  int dir = event.dir;
705  int u_or_v = event.u_or_v;
706  if (!IsEdgeNode(nbr)) {
707  pre_nodes_(dir, u_or_v, nbr) -= 1;
708  for (int i = 0; i < 2; i++) {
709  pre_sum_(u_or_v, dir, i) -= pre_nodes_(i, 1 - u_or_v, nbr);
710  }
711  }
712 }
713 
715  int nbr = event.nbr;
716  int dir = event.dir;
717  int u_or_v = event.u_or_v;
718  if (!IsEdgeNode(nbr)) {
719  pos_nodes_(dir, u_or_v, nbr) -= 1;
720  for (int i = 0; i < 2; i++) {
721  pos_sum_(u_or_v, dir, i) -= pos_nodes_(i, 1 - u_or_v, nbr);
722  }
723  }
724 }
725 
727  int nbr = event.nbr;
728  int dir = event.dir;
729  int u_or_v = event.u_or_v;
730  if (!IsEdgeNode(nbr)) {
731  for (int i = 0; i < 2; i++) {
732  pre_sum_(1 - u_or_v, i, dir) += pre_nodes_(i, 1 - u_or_v, nbr);
733  }
734  pre_nodes_(dir, u_or_v, nbr) += 1;
735  }
736 }
737 
739  int nbr = event.nbr;
740  int dir = event.dir;
741  int u_or_v = event.u_or_v;
742  if (!IsEdgeNode(nbr)) {
743  for (int i = 0; i < 2; i++) {
744  pos_sum_(1 - u_or_v, i, dir) += pos_nodes_(i, 1 - u_or_v, nbr);
745  }
746  pos_nodes_(dir, u_or_v, nbr) += 1;
747  }
748 }
749 
751  int nbr = event.nbr;
752  int dir = event.dir;
753  int u_or_v = event.u_or_v;
754  // Adjust middle sums
755  if (!IsEdgeNode(nbr)) {
756  for (int i = 0; i < 2; i++) {
757  mid_sum_(1 - u_or_v, i, dir) -= pre_nodes_(i, 1 - u_or_v, nbr);
758  mid_sum_(u_or_v, dir, i) += pos_nodes_(i, 1 - u_or_v, nbr);
759  }
760  }
761  // Update counts
762  if (IsEdgeNode(nbr)) {
763  // Determine if the event edge is u --> v or v --> u
764  int u_to_v = 0;
765  if (((nbr == node_u_) && dir == 0) || ((nbr == node_v_) && dir == 1)) {
766  u_to_v = 1;
767  }
768  // i --> j, k --> j, i --> k
769  triad_counts_(0, 0, 0) += mid_sum_(u_to_v, 0, 0)
770  + pos_sum_(u_to_v, 0, 1)
771  + pre_sum_(1 - u_to_v, 1, 1);
772  // i --> j, k --> i, j --> k
773  triad_counts_(1, 0, 0) += mid_sum_(u_to_v, 1, 0)
774  + pos_sum_(1 - u_to_v, 0, 1)
775  + pre_sum_(1 - u_to_v, 0, 1);
776  // i --> j, j --> k, i --> k
777  triad_counts_(0, 1, 0) += mid_sum_(1 - u_to_v, 0, 0)
778  + pos_sum_(u_to_v, 1, 1)
779  + pre_sum_(1 - u_to_v, 1, 0);
780  // i --> j, i --> k, j --> k
781  triad_counts_(1, 1, 0) += mid_sum_(1 - u_to_v, 1, 0)
782  + pos_sum_(1 - u_to_v, 1, 1)
783  + pre_sum_(1 - u_to_v, 0, 0);
784  // i --> j, k --> j, k --> i
785  triad_counts_(0, 0, 1) += mid_sum_(u_to_v, 0, 1)
786  + pos_sum_(u_to_v, 0, 0)
787  + pre_sum_(u_to_v, 1, 1);
788  // i --> j, k --> i, k --> j
789  triad_counts_(1, 0, 1) += mid_sum_(u_to_v, 1, 1)
790  + pos_sum_(1 - u_to_v, 0, 0)
791  + pre_sum_(u_to_v, 0, 1);
792  // i --> j, j --> k, k --> i
793  triad_counts_(0, 1, 1) += mid_sum_(1 - u_to_v, 0, 1)
794  + pos_sum_(u_to_v, 1, 0)
795  + pre_sum_(u_to_v, 1, 0);
796  // i --> j, i --> k, k --> j
797  triad_counts_(1, 1, 1) += mid_sum_(1 - u_to_v, 1, 1)
798  + pos_sum_(1 - u_to_v, 1, 0)
799  + pre_sum_(u_to_v, 0, 0);
800  }
801 }
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)
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
int PreCount(int dir1, int dir2, int dir3)
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:596
TKeyDat< TInt, TInt > TIntPair
Definition: temporalmotifs.h:6
void Count(const TIntV &event_string, const TIntV &timestamps, double delta, Counter3D &counts)
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Count3TEdgeTriadsNaive(double delta, Counter3D &counts)
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:594
void ProcessCurrent(const StarEdgeData &event)
void Count3TEdge23Node(double delta, Counter2D &counts)
void PopPre(const StarEdgeData &event)
TDat Dat
Definition: ds.h:349
void PopPre(const TriadEdgeData &event)
Execution context.
Definition: table.h:180
void PopPos(const StarEdgeData &event)
int PosCount(int dir1, int dir2, int dir3)
Definition: gbase.h:23
void PopPos(const TriadEdgeData &event)
void GetAllStaticTriangles(TIntV &Us, TIntV &Vs, TIntV &Ws)
Iterator class for TTable rows.
Definition: table.h:330
void AddStarEdgeData(TVec< TIntPair > &ts_indices, TVec< StarEdgeData > &events, int &index, int u, int v, int nbr, int key)
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void ProcessCurrent(const TriadEdgeData &event)
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
void IncrementCounts(int event)
void Count3TEdge3NodeStars(double delta, Counter3D &pre_counts, Counter3D &pos_counts, Counter3D &mid_counts)
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.h:424
#define MIN(a, b)
Definition: bd.h:346
void GetAllNeighbors(int node, TIntV &nbrs)
int Counts(int dir1, int dir2, int dir3)
Definition: dt.h:1137
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:556
void PushPos(const StarEdgeData &event)
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)
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
TKey Key
Definition: ds.h:348
static PTable LoadSS(const Schema &S, const TStr &InFNm, TTableContext *Context, const char &Separator= '\t', TBool HasTitleLine=false)
Loads table from spread sheet (TSV, CSV, etc). Note: HasTitleLine = true is not supported. Please comment title lines instead.
Definition: table.cpp:795
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
Definition: dt.h:412
void Count3TEdge2Node(double delta, Counter2D &counts)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TVec< TInt > TIntV
Definition: ds.h:1594
void PushPre(const StarEdgeData &event)
Definition: bd.h:196
void Count3TEdgeTriads(double delta, Counter3D &counts)
void PushPre(const TriadEdgeData &event)
void AddStarEdges(TVec< TIntPair > &combined, int u, int v, int key)
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:404
int MidCount(int dir1, int dir2, int dir3)
bool IsEdgeNode(int nbr)
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:412
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
#define MAX(a, b)
Definition: bd.h:350
TVec< THash< TInt, TIntV > > temporal_data_
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
void PushPos(const TriadEdgeData &event)
void Count3TEdge3NodeStarsNaive(double delta, Counter3D &pre_counts, Counter3D &pos_counts, Counter3D &mid_counts)
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430