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