SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
triad.h
Go to the documentation of this file.
1 #ifndef TRIAD_H
2 #define TRIAD_H
3 
4 namespace TSnap {
5 
7 // Triads and clustering coefficient
8 
10 
12 template <class PGraph> double GetClustCf(const PGraph& Graph, int SampleNodes=-1);
14 
18 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int SampleNodes=-1);
20 
26 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriads, int64& OpenTriads, int SampleNodes=-1);
28 
35 template <class PGraph> double GetClustCfAll(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriadsX, int64& OpenTriadsX, int SampleNodes=-1);
37 
39 template <class PGraph> double GetNodeClustCf(const PGraph& Graph, const int& NId);
41 
43 template <class PGraph> void GetNodeClustCf(const PGraph& Graph, TIntFltH& NIdCCfH);
44 
46 
50 template <class PGraph> int64 GetTriads(const PGraph& Graph, int SampleNodes=-1);
52 
55 template <class PGraph> int64 GetTriads(const PGraph& Graph, int64& ClosedTriadsX, int64& OpenTriadsX, int SampleNodes);
57 
61 template <class PGraph> int64 GetTriadsAll(const PGraph& Graph, int64& ClosedTriadsX, int64& OpenTriadsX, int SampleNodes=-1);
63 
67 template <class PGraph> void GetTriads(const PGraph& Graph, TIntTrV& NIdCOTriadV, int SampleNodes=-1);
69 
72 template <class PGraph> int GetTriadEdges(const PGraph& Graph, int SampleEdges=-1);
73 
75 
79 template <class PGraph> int GetNodeTriads(const PGraph& Graph, const int& NId);
81 
87 template <class PGraph> int GetNodeTriads(const PGraph& Graph, const int& NId, int& ClosedNTriadsX, int& OpenNTriadsX);
89 
96 template <class PGraph> int GetNodeTriadsAll(const PGraph& Graph, const int& NId, int& ClosedNTriadsX, int& OpenNTriadsX);
98 
106 template <class PGraph>
107 int GetNodeTriads(const PGraph& Graph, const int& NId, const TIntSet& GroupSet, int& InGroupEdgesX, int& InOutGroupEdgesX, int& OutGroupEdgesX);
109 
111 template <class PGraph> void GetTriadParticip(const PGraph& Graph, TIntPrV& TriadCntV);
112 
114 template<class PGraph> int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2);
116 template<class PGraph> int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV);
118 template<class PGraph> int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2);
120 
122 template<class PGraph> int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV);
124 template<class PGraph> int64 GetTriangleCnt(const PGraph& Graph);
126 template<class PGraph> void MergeNbrs(TIntV& NeighbourV, const typename PGraph::TObj::TNodeI& NI);
127 
129 template <class PGraph> void GetUniqueNbrV(const PGraph& Graph, const int& NId, TIntV& NbrV);
130 
132 int GetCommon(TIntV& A, TIntV& B);
133 
135 // Implementation
136 
137 template <class PGraph> double GetClustCf(const PGraph& Graph, int SampleNodes) {
138  TIntTrV NIdCOTriadV;
139  GetTriads(Graph, NIdCOTriadV, SampleNodes);
140  if (NIdCOTriadV.Empty()) { return 0.0; }
141  double SumCcf = 0.0;
142  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
143  const double OpenCnt = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
144  if (OpenCnt > 0) {
145  SumCcf += NIdCOTriadV[i].Val2() / OpenCnt; }
146  }
147  IAssert(SumCcf>=0);
148  return SumCcf / double(NIdCOTriadV.Len());
149 }
150 
151 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int SampleNodes) {
152  TIntTrV NIdCOTriadV;
153  GetTriads(Graph, NIdCOTriadV, SampleNodes);
154  if (NIdCOTriadV.Empty()) {
155  DegToCCfV.Clr(false);
156  return 0.0;
157  }
158  THash<TInt, TFltPr> DegSumCnt;
159  double SumCcf = 0.0;
160  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
161  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
162  const double Ccf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
163  TFltPr& SumCnt = DegSumCnt.AddDat(Graph->GetNI(NIdCOTriadV[i].Val1).GetDeg());
164  SumCnt.Val1 += Ccf;
165  SumCnt.Val2 += 1;
166  SumCcf += Ccf;
167  }
168  // get average clustering coefficient for each degree
169  DegToCCfV.Gen(DegSumCnt.Len(), 0);
170  for (int d = 0; d < DegSumCnt.Len(); d++) {
171  DegToCCfV.Add(TFltPr(DegSumCnt.GetKey(d).Val, double(DegSumCnt[d].Val1()/DegSumCnt[d].Val2())));
172  }
173  DegToCCfV.Sort();
174  return SumCcf / double(NIdCOTriadV.Len());
175 }
176 
177 template <class PGraph>
178 double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
179  TIntTrV NIdCOTriadV;
180  GetTriads(Graph, NIdCOTriadV, SampleNodes);
181  if (NIdCOTriadV.Empty()) {
182  DegToCCfV.Clr(false);
183  ClosedTriads = 0;
184  OpenTriads = 0;
185  return 0.0;
186  }
187  THash<TInt, TFltPr> DegSumCnt;
188  double SumCcf = 0.0;
189  int64 closedTriads = 0;
190  int64 openTriads = 0;
191  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
192  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
193  const double Ccf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
194  closedTriads += NIdCOTriadV[i].Val2;
195  openTriads += NIdCOTriadV[i].Val3;
196  TFltPr& SumCnt = DegSumCnt.AddDat(Graph->GetNI(NIdCOTriadV[i].Val1).GetDeg());
197  SumCnt.Val1 += Ccf;
198  SumCnt.Val2 += 1;
199  SumCcf += Ccf;
200  }
201  // get average clustering coefficient for each degree
202  DegToCCfV.Gen(DegSumCnt.Len(), 0);
203  for (int d = 0; d < DegSumCnt.Len(); d++) {
204  DegToCCfV.Add(TFltPr(DegSumCnt.GetKey(d).Val, DegSumCnt[d].Val1()/DegSumCnt[d].Val2()));
205  }
206  //if(closedTriads/3 > (uint64) TInt::Mx) { WarnNotify(TStr::Fmt("[%s line %d] %g closed triads.\n", __FILE__, __LINE__, float(closedTriads/3)).CStr()); }
207  //if(openTriads > (uint64) TInt::Mx) { WarnNotify(TStr::Fmt("[%s line %d] %g open triads.\n", __FILE__, __LINE__, float(openTriads/3)).CStr()); }
208  ClosedTriads = closedTriads/int64(3); // each triad is counted 3 times
209  OpenTriads = openTriads;
210  DegToCCfV.Sort();
211  return SumCcf / double(NIdCOTriadV.Len());
212 }
213 
214 template <class PGraph>
215 double GetClustCfAll(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
216  return GetClustCf(Graph, DegToCCfV, ClosedTriads, OpenTriads, SampleNodes);
217 }
218 
219 template <class PGraph>
220 double GetNodeClustCf(const PGraph& Graph, const int& NId) {
221  int Open, Closed;
222  GetNodeTriads(Graph, NId, Open, Closed);
223  //const double Deg = Graph->GetNI(NId).GetDeg();
224  return (Open+Closed)==0 ? 0 : double(Open)/double(Open+Closed);
225 }
226 
227 template <class PGraph>
228 void GetNodeClustCf(const PGraph& Graph, TIntFltH& NIdCCfH) {
229  TIntTrV NIdCOTriadV;
230  GetTriads(Graph, NIdCOTriadV);
231  NIdCCfH.Clr(false);
232  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
233  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
234  const double CCf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
235  NIdCCfH.AddDat(NIdCOTriadV[i].Val1, CCf);
236  }
237 }
238 
239 template <class PGraph>
240 int64 GetTriads(const PGraph& Graph, int SampleNodes) {
241  int64 OpenTriads, ClosedTriads;
242  return GetTriads(Graph, ClosedTriads, OpenTriads, SampleNodes);
243 }
244 
245 template <class PGraph>
246 int64 GetTriads(const PGraph& Graph, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
247  TIntTrV NIdCOTriadV;
248  GetTriads(Graph, NIdCOTriadV, SampleNodes);
249  uint64 closedTriads = 0;
250  uint64 openTriads = 0;
251  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
252  closedTriads += NIdCOTriadV[i].Val2;
253  openTriads += NIdCOTriadV[i].Val3;
254  }
255  //IAssert(closedTriads/3 < (uint64) TInt::Mx);
256  //IAssert(openTriads < (uint64) TInt::Mx);
257  ClosedTriads = int64(closedTriads/3); // each triad is counted 3 times
258  OpenTriads = int64(openTriads);
259  return ClosedTriads;
260 }
261 
262 template <class PGraph>
263 int64 GetTriadsAll(const PGraph& Graph, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
264  return GetTriads(Graph, ClosedTriads, OpenTriads, SampleNodes);
265 }
266 
267 // Function pretends that the graph is undirected (count unique connected triples of nodes)
268 // This implementation is slower, it uses hash tables directly
269 template <class PGraph>
270 void GetTriads_v0(const PGraph& Graph, TIntTrV& NIdCOTriadV, int SampleNodes) {
271  const bool IsDir = Graph->HasFlag(gfDirected);
272  TIntSet NbrH;
273  TIntV NIdV;
274  TRnd Rnd(0);
275 
276  Graph->GetNIdV(NIdV);
277  NIdV.Shuffle(Rnd);
278  if (SampleNodes == -1) {
279  SampleNodes = Graph->GetNodes(); }
280  NIdCOTriadV.Clr(false);
281  NIdCOTriadV.Reserve(SampleNodes);
282  for (int node = 0; node < SampleNodes; node++) {
283  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[node]);
284  if (NI.GetDeg() < 2) {
285  NIdCOTriadV.Add(TIntTr(NI.GetId(), 0, 0)); // zero triangles
286  continue;
287  }
288  // find neighborhood
289  NbrH.Clr(false);
290  for (int e = 0; e < NI.GetOutDeg(); e++) {
291  if (NI.GetOutNId(e) != NI.GetId()) {
292  NbrH.AddKey(NI.GetOutNId(e)); }
293  }
294  if (IsDir) {
295  for (int e = 0; e < NI.GetInDeg(); e++) {
296  if (NI.GetInNId(e) != NI.GetId()) {
297  NbrH.AddKey(NI.GetInNId(e)); }
298  }
299  }
300  // count connected neighbors
301  int OpenCnt=0, CloseCnt=0;
302  for (int srcNbr = 0; srcNbr < NbrH.Len(); srcNbr++) {
303  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrH.GetKey(srcNbr));
304  for (int dstNbr = srcNbr+1; dstNbr < NbrH.Len(); dstNbr++) {
305  const int dstNId = NbrH.GetKey(dstNbr);
306  if (SrcNode.IsNbrNId(dstNId)) { CloseCnt++; } // is edge
307  else { OpenCnt++; }
308  }
309  }
310  IAssert(2*(OpenCnt+CloseCnt) == NbrH.Len()*(NbrH.Len()-1));
311  NIdCOTriadV.Add(TIntTr(NI.GetId(), CloseCnt, OpenCnt));
312  }
313 }
314 
315 // Function pretends that the graph is undirected (count unique connected triples of nodes)
316 // This implementation is faster, it converts hash tables to vectors
317 template <class PGraph>
318 void GetTriads(const PGraph& Graph, TIntTrV& NIdCOTriadV, int SampleNodes) {
319  const bool IsDir = Graph->HasFlag(gfDirected);
320  TIntSet NbrH;
321  TIntV NIdV;
322  //TRnd Rnd(0);
323  TRnd Rnd(1);
324  int NNodes;
325  TIntV Nbrs;
326  int NId;
327 
328  int64 hcount;
329 
330  hcount = 0;
331 
332  NNodes = Graph->GetNodes();
333  Graph->GetNIdV(NIdV);
334  NIdV.Shuffle(Rnd);
335  if (SampleNodes == -1) {
336  SampleNodes = NNodes;
337  }
338 
339  int MxId = -1;
340  for (int i = 0; i < NNodes; i++) {
341  if (NIdV[i] > MxId) {
342  MxId = NIdV[i];
343  }
344  }
345 
346  TVec<TIntV> NbrV(MxId + 1);
347 
348  if (IsDir) {
349  // get in and out neighbors
350  for (int node = 0; node < NNodes; node++) {
351  int NId = NIdV[node];
352  NbrV[NId] = TIntV();
353  GetUniqueNbrV(Graph, NId, NbrV[NId]);
354  }
355  } else {
356  // get only out neighbors
357  for (int node = 0; node < NNodes; node++) {
358  int NId = NIdV[node];
359  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
360  NbrV[NId] = TIntV();
361  NbrV[NId].Reserve(NI.GetOutDeg());
362  NbrV[NId].Reduce(0);
363  for (int i = 0; i < NI.GetOutDeg(); i++) {
364  NbrV[NId].Add(NI.GetOutNId(i));
365  }
366  }
367  }
368 
369  NIdCOTriadV.Clr(false);
370  NIdCOTriadV.Reserve(SampleNodes);
371  for (int node = 0; node < SampleNodes; node++) {
372  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[node]);
373  int NLen;
374 
375  NId = NI.GetId();
376  hcount++;
377  if (NI.GetDeg() < 2) {
378  NIdCOTriadV.Add(TIntTr(NId, 0, 0)); // zero triangles
379  continue;
380  }
381 
382  Nbrs = NbrV[NId];
383  NLen = Nbrs.Len();
384 
385  // count connected neighbors
386  int OpenCnt1 = 0, CloseCnt1 = 0;
387  for (int srcNbr = 0; srcNbr < NLen; srcNbr++) {
388  int Count = GetCommon(NbrV[NbrV[NId][srcNbr]],Nbrs);
389  CloseCnt1 += Count;
390  }
391  CloseCnt1 /= 2;
392  OpenCnt1 = (NLen*(NLen-1))/2 - CloseCnt1;
393  NIdCOTriadV.Add(TIntTr(NId, CloseCnt1, OpenCnt1));
394  }
395 }
396 
397 #if 0
398 // OP RS 2016/08/25, this is an alternative implementation of GetTriangleCnt()
399 template<class PGraph>
400 int64 CountTriangles(const PGraph& Graph) {
402  TIntV MapV;
403 
404  int ind = 0;
405  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
406  H.AddDat(NI.GetId(), ind);
407  MapV.Add(NI.GetId());
408  ind += 1;
409  }
410 
411  TVec<TIntV> HigherDegNbrV(ind);
412 
413 #ifdef USE_OPENMP
414 #pragma omp parallel for schedule(dynamic)
415 #endif
416  for (int i = 0; i < ind; i++) {
417  typename PGraph::TObj::TNodeI NI = Graph->GetNI(MapV[i]);
418  TIntV NbrV;
419 
420  MergeNbrs<PGraph>(NbrV, NI);
421 
422  TIntV V;
423  for (int j = 0; j < NbrV.Len(); j++) {
424  TInt Vert = NbrV[j];
425  TInt Deg = Graph->GetNI(Vert).GetDeg();
426  if (Deg > NI.GetDeg() ||
427  (Deg == NI.GetDeg() && Vert > NI.GetId())) {
428  V.Add(Vert);
429  }
430  }
431 
432  HigherDegNbrV[i] = V;
433 
434  }
435 
436  int64 cnt = 0;
437 #ifdef USE_OPENMP
438 #pragma omp parallel for schedule(dynamic) reduction(+:cnt)
439 #endif
440  for (int i = 0; i < HigherDegNbrV.Len(); i++) {
441  for (int j = 0; j < HigherDegNbrV[i].Len(); j++) {
442  TInt NbrInd = H.GetDat(HigherDegNbrV[i][j]);
443 
444  int64 num = GetCommon(HigherDegNbrV[i], HigherDegNbrV[NbrInd]);
445  cnt += num;
446  }
447  }
448 
449  return cnt;
450 }
451 #endif
452 
453 template<class PGraph>
454 int64 GetTriangleCnt(const PGraph& Graph) {
455  const int NNodes = Graph->GetNodes();
456 
457  TIntV MapV(NNodes);
459  NV.Reduce(0);
460 
461  int MxId = -1;
462  int ind = 0;
463  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
464  NV.Add(NI);
465  int Id = NI.GetId();
466  if (Id > MxId) {
467  MxId = Id;
468  }
469  MapV[ind] = Id;
470  ind++;
471  }
472 
473  TIntV IndV(MxId+1);
474 
475  for (int j = 0; j < NNodes; j++) {
476  IndV[MapV[j]] = j;
477  }
478 
479  ind = MapV.Len();
480 
481  TVec<TIntV> HigherDegNbrV(ind);
482 
483  for (int i = 0; i < ind; i++) {
484  HigherDegNbrV[i] = TVec<TInt>();
485  HigherDegNbrV[i].Reserve(NV[i].GetDeg());
486  HigherDegNbrV[i].Reduce(0);
487  }
488 
489 #ifdef USE_OPENMP
490 #pragma omp parallel for schedule(dynamic)
491 #endif
492  for (int i = 0; i < ind; i++) {
493  typename PGraph::TObj::TNodeI NI = NV[i];
494  MergeNbrs<PGraph>(HigherDegNbrV[i], NI);
495 
496  int k = 0;
497  for (int j = 0; j < HigherDegNbrV[i].Len(); j++) {
498  TInt Vert = HigherDegNbrV[i][j];
499  TInt Deg = NV[IndV[Vert]].GetDeg();
500  if (Deg > NI.GetDeg() ||
501  (Deg == NI.GetDeg() && Vert > NI.GetId())) {
502  HigherDegNbrV[i][k] = Vert;
503  k++;
504  }
505  }
506  HigherDegNbrV[i].Reduce(k);
507  }
508 
509  int64 cnt = 0;
510 #ifdef USE_OPENMP
511 #pragma omp parallel for schedule(dynamic) reduction(+:cnt)
512 #endif
513  for (int i = 0; i < HigherDegNbrV.Len(); i++) {
514  for (int j = 0; j < HigherDegNbrV[i].Len(); j++) {
515  TInt NbrInd = IndV[HigherDegNbrV[i][j]];
516 
517  int64 num = GetCommon(HigherDegNbrV[i], HigherDegNbrV[NbrInd]);
518  cnt += num;
519  }
520  }
521 
522  return cnt;
523 }
524 
525 template<class PGraph>
526 void MergeNbrs(TIntV& NeighbourV, const typename PGraph::TObj::TNodeI& NI) {
527  int j = 0;
528  int k = 0;
529  int prev = -1;
530  int indeg = NI.GetInDeg();
531  int outdeg = NI.GetOutDeg();
532  if (indeg > 0 && outdeg > 0) {
533  int v1 = NI.GetInNId(j);
534  int v2 = NI.GetOutNId(k);
535  while (1) {
536  if (v1 <= v2) {
537  if (prev != v1) {
538  NeighbourV.Add(v1);
539  prev = v1;
540  }
541  j += 1;
542  if (j >= indeg) {
543  break;
544  }
545  v1 = NI.GetInNId(j);
546  } else {
547  if (prev != v2) {
548  NeighbourV.Add(v2);
549  prev = v2;
550  }
551  k += 1;
552  if (k >= outdeg) {
553  break;
554  }
555  v2 = NI.GetOutNId(k);
556  }
557  }
558  }
559  while (j < indeg) {
560  int v = NI.GetInNId(j);
561  if (prev != v) {
562  NeighbourV.Add(v);
563  prev = v;
564  }
565  j += 1;
566  }
567  while (k < outdeg) {
568  int v = NI.GetOutNId(k);
569  if (prev != v) {
570  NeighbourV.Add(v);
571  prev = v;
572  }
573  k += 1;
574  }
575 }
576 
577 // Count the number of edges that participate in at least one triad
578 template <class PGraph>
579 int GetTriadEdges(const PGraph& Graph, int SampleEdges) {
580  const bool IsDir = Graph->HasFlag(gfDirected);
581  TIntSet NbrH;
582  int TriadEdges = 0;
583  for(typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
584  NbrH.Clr(false);
585  for (int e = 0; e < NI.GetOutDeg(); e++) {
586  if (NI.GetOutNId(e) != NI.GetId()) {
587  NbrH.AddKey(NI.GetOutNId(e)); }
588  }
589  if (IsDir) {
590  for (int e = 0; e < NI.GetInDeg(); e++) {
591  if (NI.GetInNId(e) != NI.GetId()) {
592  NbrH.AddKey(NI.GetInNId(e)); }
593  }
594  }
595  for (int e = 0; e < NI.GetOutDeg(); e++) {
596  if (!IsDir && NI.GetId()<NI.GetOutNId(e)) { continue; } // for undirected graphs count each edge only once
597  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NI.GetOutNId(e));
598  bool Triad=false;
599  for (int e1 = 0; e1 < SrcNode.GetOutDeg(); e1++) {
600  if (NbrH.IsKey(SrcNode.GetOutNId(e1))) { Triad=true; break; }
601  }
602  if (IsDir && ! Triad) {
603  for (int e1 = 0; e1 < SrcNode.GetInDeg(); e1++) {
604  if (NbrH.IsKey(SrcNode.GetInNId(e1))) { Triad=true; break; }
605  }
606  }
607  if (Triad) { TriadEdges++; }
608  }
609  }
610  return TriadEdges;
611 }
612 
613 // Returns number of undirected triads a node participates in
614 template <class PGraph>
615 int GetNodeTriads(const PGraph& Graph, const int& NId) {
616  int ClosedTriads=0, OpenTriads=0;
617  return GetNodeTriads(Graph, NId, ClosedTriads, OpenTriads);
618 }
619 
620 // Return number of undirected triads a node participates in
621 template <class PGraph>
622 int GetNodeTriads(const PGraph& Graph, const int& NId, int& ClosedTriads, int& OpenTriads) {
623  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
624  ClosedTriads=0; OpenTriads=0;
625  if (NI.GetDeg() < 2) { return 0; }
626  // find neighborhood
627  TIntSet NbrSet(NI.GetDeg());
628  for (int e = 0; e < NI.GetOutDeg(); e++) {
629  if (NI.GetOutNId(e) != NI.GetId()) { // exclude self edges
630  NbrSet.AddKey(NI.GetOutNId(e)); }
631  }
632  if (Graph->HasFlag(gfDirected)) {
633  for (int e = 0; e < NI.GetInDeg(); e++) {
634  if (NI.GetInNId(e) != NI.GetId()) { // exclude self edges
635  NbrSet.AddKey(NI.GetInNId(e)); }
636  }
637  }
638  // count connected neighbors
639  for (int srcNbr = 0; srcNbr < NbrSet.Len(); srcNbr++) {
640  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrSet.GetKey(srcNbr));
641  for (int dstNbr = srcNbr+1; dstNbr < NbrSet.Len(); dstNbr++) {
642  const int dstNId = NbrSet.GetKey(dstNbr);
643  if (SrcNode.IsNbrNId(dstNId)) { ClosedTriads++; }
644  else { OpenTriads++; }
645  }
646  }
647  return ClosedTriads;
648 }
649 
650 template <class PGraph>
651 int GetNodeTriadsAll(const PGraph& Graph, const int& NId, int& ClosedTriads, int& OpenTriads) {
652  return GetNodeTriads(Graph, NId, ClosedTriads, OpenTriads);
653 }
654 
655 // Node NId and a subset of its neighbors GroupSet
656 // InGroupEdges ... triads (NId, g1, g2), where g1 and g2 are in GroupSet
657 // InOutGroupEdges ... triads (NId, g1, o1), where g1 in GroupSet and o1 not in GroupSet
658 // OutGroupEdges ... triads (NId, o1, o2), where o1 and o2 are not in GroupSet
659 template <class PGraph>
660 int GetNodeTriads(const PGraph& Graph, const int& NId, const TIntSet& GroupSet, int& InGroupEdges, int& InOutGroupEdges, int& OutGroupEdges) {
661  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
662  const bool IsDir = Graph->HasFlag(gfDirected);
663  InGroupEdges=0; InOutGroupEdges=0; OutGroupEdges=0;
664  if (NI.GetDeg() < 2) { return 0; }
665  // find neighborhood
666  TIntSet NbrSet(NI.GetDeg());
667  for (int e = 0; e < NI.GetOutDeg(); e++) {
668  if (NI.GetOutNId(e) != NI.GetId()) { // exclude self edges
669  NbrSet.AddKey(NI.GetOutNId(e)); }
670  }
671  if (IsDir) {
672  for (int e = 0; e < NI.GetInDeg(); e++) {
673  if (NI.GetInNId(e) != NI.GetId()) {
674  NbrSet.AddKey(NI.GetInNId(e)); }
675  }
676  }
677  // count connected neighbors
678  for (int srcNbr = 0; srcNbr < NbrSet.Len(); srcNbr++) {
679  const int NbrId = NbrSet.GetKey(srcNbr);
680  const bool NbrIn = GroupSet.IsKey(NbrId);
681  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrId);
682  for (int dstNbr = srcNbr+1; dstNbr < NbrSet.Len(); dstNbr++) {
683  const int DstNId = NbrSet.GetKey(dstNbr);
684  if (SrcNode.IsNbrNId(DstNId)) { // triad (NId, NbrId, DstNid)
685  bool DstIn = GroupSet.IsKey(DstNId);
686  if (NbrIn && DstIn) { InGroupEdges++; }
687  else if (NbrIn || DstIn) { InOutGroupEdges++; }
688  else { OutGroupEdges++; }
689  }
690  }
691  }
692  return InGroupEdges;
693 }
694 
695 // For each node count how many triangles it participates in
696 template <class PGraph>
697 void GetTriadParticip(const PGraph& Graph, TIntPrV& TriadCntV) {
698  TIntH TriadCntH;
699  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
700  const int Triads = GetNodeTriads(Graph, NI.GetId());
701  TriadCntH.AddDat(Triads) += 1;
702  }
703  TriadCntH.GetKeyDatPrV(TriadCntV);
704  TriadCntV.Sort();
705 }
706 
707 template<class PGraph>
708 int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2) {
709  TIntV NbrV;
710  return GetCmnNbrs(Graph, NId1, NId2, NbrV);
711 }
712 
713 // Get common neighbors between a pair of nodes (undirected)
714 template<class PGraph>
715 int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
716  if (! Graph->IsNode(NId1) || ! Graph->IsNode(NId2)) { NbrV.Clr(false); return 0; }
717  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId1);
718  typename PGraph::TObj::TNodeI NI2 = Graph->GetNI(NId2);
719  NbrV.Clr(false);
720  NbrV.Reserve(TMath::Mn(NI1.GetDeg(), NI2.GetDeg()));
721  TIntSet NSet1(NI1.GetDeg()), NSet2(NI2.GetDeg());
722  for (int i = 0; i < NI1.GetDeg(); i++) {
723  const int nid = NI1.GetNbrNId(i);
724  if (nid!=NId1 && nid!=NId2) {
725  NSet1.AddKey(nid); }
726  }
727  for (int i = 0; i < NI2.GetDeg(); i++) {
728  const int nid = NI2.GetNbrNId(i);
729  if (NSet1.IsKey(nid)) {
730  NSet2.AddKey(nid);
731  }
732  }
733  NSet2.GetKeyV(NbrV);
734  return NbrV.Len();
735 }
736 
737 template<>
738 inline int GetCmnNbrs<PUNGraph>(const PUNGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
739  if (! Graph->IsNode(NId1) || ! Graph->IsNode(NId2)) { NbrV.Clr(false); return 0; }
740  const TUNGraph::TNodeI NI1 = Graph->GetNI(NId1);
741  const TUNGraph::TNodeI NI2 = Graph->GetNI(NId2);
742  int i=0, j=0;
743  NbrV.Clr(false);
744  NbrV.Reserve(TMath::Mn(NI1.GetDeg(), NI2.GetDeg()));
745  while (i < NI1.GetDeg() && j < NI2.GetDeg()) {
746  const int nid = NI1.GetNbrNId(i);
747  while (j < NI2.GetDeg() && NI2.GetNbrNId(j) < nid) { j++; }
748  if (j < NI2.GetDeg() && nid==NI2.GetNbrNId(j) && nid!=NId1 && nid!=NId2) {
749  IAssert(NbrV.Empty() || NbrV.Last() < nid);
750  NbrV.Add(nid);
751  j++;
752  }
753  i++;
754  }
755  return NbrV.Len();
756 }
757 
758 // get number of length 2 directed paths between a pair of nodes
759 // for a pair of nodes (i,j): |{u: (i,u) and (u,j) }|
760 template<class PGraph>
761 int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2) {
762  TIntV NbrV;
763  return GetLen2Paths(Graph, NId1, NId2, NbrV);
764 }
765 
766 // get number of length 2 directed paths between a pair of nodes
767 // for a pair of nodes (i,j): {u: (i,u) and (u,j) }
768 template<class PGraph>
769 int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
770  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId1);
771  NbrV.Clr(false);
772  NbrV.Reserve(NI.GetOutDeg());
773  for (int e = 0; e < NI.GetOutDeg(); e++) {
774  const typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(NI.GetOutNId(e));
775  if (MidNI.IsOutNId(NId2)) {
776  NbrV.Add(MidNI.GetId());
777  }
778  }
779  return NbrV.Len();
780 }
781 
782 template <class PGraph>
783 void GetUniqueNbrV(const PGraph& Graph, const int& NId, TIntV& NbrV) {
784  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
785  NbrV.Reserve(NI.GetDeg());
786  NbrV.Reduce(0);
787 
788  int j = 0;
789  int k = 0;
790  int Prev = -1;
791  int InDeg = NI.GetInDeg();
792  int OutDeg = NI.GetOutDeg();
793  if (InDeg > 0 && OutDeg > 0) {
794  int v1 = NI.GetInNId(j);
795  int v2 = NI.GetOutNId(k);
796  while (1) {
797  if (v1 <= v2) {
798  if (Prev != v1) {
799  if (v1 != NId) {
800  NbrV.Add(v1);
801  Prev = v1;
802  }
803  }
804  j += 1;
805  if (j >= InDeg) {
806  break;
807  }
808  v1 = NI.GetInNId(j);
809  } else {
810  if (Prev != v2) {
811  if (v2 != NId) {
812  NbrV.Add(v2);
813  }
814  Prev = v2;
815  }
816  k += 1;
817  if (k >= OutDeg) {
818  break;
819  }
820  v2 = NI.GetOutNId(k);
821  }
822  }
823  }
824  while (j < InDeg) {
825  int v = NI.GetInNId(j);
826  if (Prev != v) {
827  if (v != NId) {
828  NbrV.Add(v);
829  }
830  Prev = v;
831  }
832  j += 1;
833  }
834  while (k < OutDeg) {
835  int v = NI.GetOutNId(k);
836  if (Prev != v) {
837  if (v != NId) {
838  NbrV.Add(v);
839  }
840  Prev = v;
841  }
842  k += 1;
843  }
844 }
845 
846 }; // mamespace TSnap
847 
849 // Node and Edge Network Constraint (by Ron Burt)
850 // works for directed and undirected graphs (but not for multigraphs)
851 template <class PGraph>
853 public:
854  PGraph Graph;
855  THash<TIntPr, TFlt> NodePrCH; // pairs of nodes that have non-zero network constraint
856 public:
857  TNetConstraint(const PGraph& GraphPt, const bool& CalcaAll=true);
858  int Len() const { return NodePrCH.Len(); }
859  double GetC(const int& ConstraintN) const { return NodePrCH[ConstraintN]; }
860  TIntPr GetNodePr(const int& ConstraintN) const { return NodePrCH.GetKey(ConstraintN); }
861  double GetEdgeC(const int& NId1, const int& NId2) const;
862  double GetNodeC(const int& NId) const;
863  void AddConstraint(const int& NId1, const int& NId2);
864  void CalcConstraints();
865  void CalcConstraints(const int& NId);
866  void Dump() const;
867  static void Test();
868 };
869 
870 template <class PGraph>
871 TNetConstraint<PGraph>::TNetConstraint(const PGraph& GraphPt, const bool& CalcaAll) : Graph(GraphPt) {
872  CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph)); // must not be multigraph
873  if (CalcaAll) {
874  CalcConstraints();
875  }
876 }
877 
878 template <class PGraph>
879 double TNetConstraint<PGraph>::GetEdgeC(const int& NId1, const int& NId2) const {
880  if (NodePrCH.IsKey(TIntPr(NId1, NId2))) {
881  return NodePrCH.GetDat(TIntPr(NId1, NId2)); }
882  else {
883  return 0.0; }
884 }
885 
886 template <class PGraph>
887 double TNetConstraint<PGraph>::GetNodeC(const int& NId) const {
888  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId);
889  if (NI1.GetOutDeg() == 0) { return 0.0; }
890  int KeyId = -1;
891  for (int k = 0; k<NI1.GetOutDeg(); k++) {
892  KeyId = NodePrCH.GetKeyId(TIntPr(NI1.GetId(), NI1.GetOutNId(k)));
893  if (KeyId > -1) { break; }
894  }
895  if (KeyId < 0) { return 0.0; }
896  double Constraint = NodePrCH[KeyId];
897  for (int i = KeyId-1; i >-1 && NodePrCH.GetKey(i).Val1()==NId; i--) {
898  Constraint += NodePrCH[i];
899  }
900  for (int i = KeyId+1; i < NodePrCH.Len() && NodePrCH.GetKey(i).Val1()==NId; i++) {
901  Constraint += NodePrCH[i];
902  }
903  return Constraint;
904 }
905 
906 template <class PGraph>
907 void TNetConstraint<PGraph>::AddConstraint(const int& NId1, const int& NId2) {
908  if (NId1==NId2 || NodePrCH.IsKey(TIntPr(NId1, NId2))) {
909  return;
910  }
911  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId1);
912  double Constraint = 0.0;
913  if (NI1.IsOutNId(NId2)) { // is direct edge
914  Constraint += 1.0/(double) NI1.GetOutDeg();
915  }
916  const double SrcC = 1.0/(double) NI1.GetOutDeg();
917  for (int e = 0; e < NI1.GetOutDeg(); e++) {
918  const int MidNId = NI1.GetOutNId(e);
919  if (MidNId == NId1 || MidNId == NId2) { continue; }
920  const typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(MidNId);
921  if (MidNI.IsOutNId(NId2)) {
922  Constraint += SrcC * (1.0/(double)MidNI.GetOutDeg());
923  }
924  }
925  if (Constraint==0) { return; }
926  Constraint = TMath::Sqr(Constraint);
927  NodePrCH.AddDat(TIntPr(NId1, NId2), Constraint);
928 }
929 
930 template <class PGraph>
932  // add edges
933  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
934  AddConstraint(EI.GetSrcNId(), EI.GetDstNId());
935  AddConstraint(EI.GetDstNId(), EI.GetSrcNId());
936  }
937  // add open triads
938  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
939  for (int i = 0; i < NI.GetDeg(); i++) {
940  const int NId1 = NI.GetNbrNId(i);
941  for (int j = 0; j < NI.GetDeg(); j++) {
942  const int NId2 = NI.GetNbrNId(j);
943  AddConstraint(NId1, NId2);
944  }
945  }
946  }
947  NodePrCH.SortByKey();
948 }
949 
950 // calculate constraints around a node id
951 template <class PGraph>
953  typename PGraph::TObj::TNodeI StartNI = Graph->GetNI(NId);
954  TIntSet SeenSet;
955  for (int e = 0; e < StartNI.GetOutDeg(); e++) {
956  typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(StartNI.GetOutNId(e));
957  AddConstraint(NId, MidNI.GetId());
958  for (int i = 0; i < MidNI.GetOutDeg(); i++) {
959  const int EndNId = MidNI.GetOutNId(i);
960  if (! SeenSet.IsKey(EndNId)) {
961  AddConstraint(NId, EndNId);
962  SeenSet.AddKey(EndNId);
963  }
964  }
965  }
966 }
967 
968 template <class PGraph>
970  printf("Edge network constraint: (%d, %d)\n", Graph->GetNodes(), Graph->GetEdges());
971  for (int e = 0; e < NodePrCH.Len(); e++) {
972  printf(" %4d %4d : %f\n", NodePrCH.GetKey(e).Val1(), NodePrCH.GetKey(e).Val2(), NodePrCH[e].Val);
973  }
974  printf("\n");
975 }
976 
977 // example from page 56 of Structural Holes by Ronald S. Burt
978 // (http://www.amazon.com/Structural-Holes-Social-Structure-Competition/dp/0674843711)
979 template <class PGraph>
981  PUNGraph G = TUNGraph::New();
982  G->AddNode(0); G->AddNode(1); G->AddNode(2); G->AddNode(3);
983  G->AddNode(4); G->AddNode(5); G->AddNode(6);
984  G->AddEdge(0,1); G->AddEdge(0,2); G->AddEdge(0,3); G->AddEdge(0,4); G->AddEdge(0,5); G->AddEdge(0,6);
985  G->AddEdge(1,2); G->AddEdge(1,5); G->AddEdge(1,6);
986  G->AddEdge(2,4);
987  TNetConstraint<PUNGraph> NetConstraint(G, true);
988  // NetConstraint.CalcConstraints(0);
989  NetConstraint.Dump();
990  printf("middle node network constraint: %f\n", NetConstraint.GetNodeC(0));
991 }
992 
993 #endif // TRIAD_H
994 
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
void GetUniqueNbrV(const PGraph &Graph, const int &NId, TIntV &NbrV)
Returns sorted vector NbrV containing unique in or out neighbors of node NId in graph Graph...
Definition: triad.h:783
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Main namespace for all the Snap global entities.
Definition: alg.h:1
int64 GetTriads(const PGraph &Graph, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:246
void CalcConstraints()
Definition: triad.h:931
Definition: dt.h:11
int64 GetTriangleCnt(const PGraph &Graph)
Returns the number of triangles in graph Graph.
Definition: triad.h:454
int Val
Definition: dt.h:1139
double GetNodeClustCf(const PGraph &Graph, const int &NId)
Returns clustering coefficient of a particular node.
Definition: triad.h:220
static void Test()
Definition: triad.h:980
int GetLen2Paths(const PGraph &Graph, const int &NId1, const int &NId2)
Returns the number of length 2 directed paths between a pair of nodes NId1, NId2 (NId1 –> U –> NId2...
Definition: triad.h:761
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
PGraph Graph
Definition: triad.h:854
int GetCmnNbrs< PUNGraph >(const PUNGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV)
Definition: triad.h:738
void MergeNbrs(TIntV &NeighbourV, const typename PGraph::TObj::TNodeI &NI)
Merges neighbors by removing duplicates and produces one sorted vector of neighbors.
Definition: triad.h:526
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
static double Sqr(const double &x)
Definition: xmath.h:12
TNetConstraint(const PGraph &GraphPt, const bool &CalcaAll=true)
Definition: triad.h:871
void Reduce(const TSizeTy &_Vals=-1)
Reduces the vector's length to _Vals elements, which must be less than the current length...
Definition: ds.h:556
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1141
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:90
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
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
unsigned long long uint64
Definition: bd.h:38
void GetTriads_v0(const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes)
Definition: triad.h:270
void AddConstraint(const int &NId1, const int &NId2)
Definition: triad.h:907
int GetNodeTriadsAll(const PGraph &Graph, const int &NId, int &ClosedNTriadsX, int &OpenNTriadsX)
Returns number of Open and Closed triads a node NId participates in.
Definition: triad.h:651
double GetNodeC(const int &NId) const
Definition: triad.h:887
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddKey(const TKey &Key)
Definition: shash.h:1254
int GetNodeTriads(const PGraph &Graph, const int &NId)
Returns the number of undirected triads a node NId participates in.
Definition: triad.h:615
double GetClustCfAll(const PGraph &Graph, TFltPrV &DegToCCfV, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes=-1)
Computes the distribution of average clustering coefficient as well as the number of open and closed ...
Definition: triad.h:215
int64 GetTriadsAll(const PGraph &Graph, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:263
double GetC(const int &ConstraintN) const
Definition: triad.h:859
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
void Dump() const
Definition: triad.h:969
Definition: dt.h:1137
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
double GetEdgeC(const int &NId1, const int &NId2) const
Definition: triad.h:879
#define CAssert(Cond)
Definition: bd.h:302
int Len() const
Definition: shash.h:1121
long long int64
Definition: bd.h:27
int GetTriadEdges(const PGraph &Graph, int SampleEdges=-1)
Counts the number of edges that participate in at least one triad.
Definition: triad.h:579
int GetCommon(TIntV &A, TIntV &B)
Returns the number of common elements in two sorted TInt vectors.
Definition: triad.cpp:59
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
void GetTriadParticip(const PGraph &Graph, TIntPrV &TriadCntV)
Triangle Participation Ratio: For each node counts how many triangles it participates in and then ret...
Definition: triad.h:697
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
double GetClustCf(const PGraph &Graph, int SampleNodes=-1)
Computes the average clustering coefficient as defined in Watts and Strogatz, Collective dynamics of ...
Definition: triad.h:137
TVal1 Val1
Definition: ds.h:34
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:111
TVec< TInt > TIntV
Definition: ds.h:1594
TVal2 Val2
Definition: ds.h:35
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TIntPr GetNodePr(const int &ConstraintN) const
Definition: triad.h:860
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:171
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
THash< TIntPr, TFlt > NodePrCH
Definition: triad.h:855
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
int GetCmnNbrs(const PGraph &Graph, const int &NId1, const int &NId2)
Returns a number of shared neighbors between a pair of nodes NId1 and NId2.
Definition: triad.h:708
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
int Len() const
Definition: triad.h:858
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430