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