SNAP Library 2.3, Developer Reference  2014-06-16 11:58:46
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 namespace TSnap {
2 
4 // Triads and clustering coefficient
5 
7 
9 template <class PGraph> double GetClustCf(const PGraph& Graph, int SampleNodes=-1);
11 
15 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int SampleNodes=-1);
17 
21 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriadsX, int64& OpenTriadsX, int SampleNodes=-1);
23 
25 template <class PGraph> double GetNodeClustCf(const PGraph& Graph, const int& NId);
27 
31 template <class PGraph> void GetNodeClustCf(const PGraph& Graph, TIntFltH& NIdCCfH);
32 
34 
38 template <class PGraph> int64 GetTriads(const PGraph& Graph, int SampleNodes=-1);
40 
43 template <class PGraph> int64 GetTriads(const PGraph& Graph, int64& ClosedTriadsX, int64& OpenTriadsX, int SampleNodes);
45 
49 template <class PGraph> void GetTriads(const PGraph& Graph, TIntTrV& NIdCOTriadV, int SampleNodes=-1);
51 
54 template <class PGraph> int GetTriadEdges(const PGraph& Graph, int SampleEdges=-1);
55 
57 
61 template <class PGraph> int GetNodeTriads(const PGraph& Graph, const int& NId);
63 
69 template <class PGraph> int GetNodeTriads(const PGraph& Graph, const int& NId, int& ClosedNTriadsX, int& OpenNTriadsX);
71 
79 template <class PGraph>
80 int GetNodeTriads(const PGraph& Graph, const int& NId, const TIntSet& GroupSet, int& InGroupEdgesX, int& InOutGroupEdgesX, int& OutGroupEdgesX);
82 
84 template <class PGraph> void GetTriadParticip(const PGraph& Graph, TIntPrV& TriadCntV);
85 
87 template<class PGraph> int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2);
89 template<class PGraph> int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV);
91 template<class PGraph> int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2);
93 
95 template<class PGraph> int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV);
96 
98 // Implementation
99 
100 template <class PGraph> double GetClustCf(const PGraph& Graph, int SampleNodes) {
101  TIntTrV NIdCOTriadV;
102  GetTriads(Graph, NIdCOTriadV, SampleNodes);
103  if (NIdCOTriadV.Empty()) { return 0.0; }
104  double SumCcf = 0.0;
105  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
106  const double OpenCnt = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
107  if (OpenCnt > 0) {
108  SumCcf += NIdCOTriadV[i].Val2() / OpenCnt; }
109  }
110  IAssert(SumCcf>=0);
111  return SumCcf / double(NIdCOTriadV.Len());
112 }
113 
114 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int SampleNodes) {
115  TIntTrV NIdCOTriadV;
116  GetTriads(Graph, NIdCOTriadV, SampleNodes);
117  THash<TInt, TFltPr> DegSumCnt;
118  double SumCcf = 0.0;
119  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
120  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
121  const double Ccf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
122  TFltPr& SumCnt = DegSumCnt.AddDat(Graph->GetNI(NIdCOTriadV[i].Val1).GetDeg());
123  SumCnt.Val1 += Ccf;
124  SumCnt.Val2 += 1;
125  SumCcf += Ccf;
126  }
127  // get average clustering coefficient for each degree
128  DegToCCfV.Gen(DegSumCnt.Len(), 0);
129  for (int d = 0; d < DegSumCnt.Len(); d++) {
130  DegToCCfV.Add(TFltPr(DegSumCnt.GetKey(d).Val, double(DegSumCnt[d].Val1()/DegSumCnt[d].Val2())));
131  }
132  DegToCCfV.Sort();
133  return SumCcf / double(NIdCOTriadV.Len());
134 }
135 
136 template <class PGraph>
137 double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
138  TIntTrV NIdCOTriadV;
139  GetTriads(Graph, NIdCOTriadV, SampleNodes);
140  THash<TInt, TFltPr> DegSumCnt;
141  double SumCcf = 0.0;
142  int64 closedTriads = 0;
143  int64 openTriads = 0;
144  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
145  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
146  const double Ccf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
147  closedTriads += NIdCOTriadV[i].Val2;
148  openTriads += NIdCOTriadV[i].Val3;
149  TFltPr& SumCnt = DegSumCnt.AddDat(Graph->GetNI(NIdCOTriadV[i].Val1).GetDeg());
150  SumCnt.Val1 += Ccf;
151  SumCnt.Val2 += 1;
152  SumCcf += Ccf;
153  }
154  // get average clustering coefficient for each degree
155  DegToCCfV.Gen(DegSumCnt.Len(), 0);
156  for (int d = 0; d < DegSumCnt.Len(); d++) {
157  DegToCCfV.Add(TFltPr(DegSumCnt.GetKey(d).Val, DegSumCnt[d].Val1()/DegSumCnt[d].Val2()));
158  }
159  //if(closedTriads/3 > (uint64) TInt::Mx) { WarnNotify(TStr::Fmt("[%s line %d] %g closed triads.\n", __FILE__, __LINE__, float(closedTriads/3)).CStr()); }
160  //if(openTriads > (uint64) TInt::Mx) { WarnNotify(TStr::Fmt("[%s line %d] %g open triads.\n", __FILE__, __LINE__, float(openTriads/3)).CStr()); }
161  ClosedTriads = closedTriads/int64(3); // each triad is counted 3 times
162  OpenTriads = openTriads;
163  DegToCCfV.Sort();
164  return SumCcf / double(NIdCOTriadV.Len());
165 }
166 
167 template <class PGraph>
168 double GetNodeClustCf(const PGraph& Graph, const int& NId) {
169  int Open, Closed;
170  GetNodeTriads(Graph, NId, Open, Closed);
171  //const double Deg = Graph->GetNI(NId).GetDeg();
172  return (Open+Closed)==0 ? 0 : double(Open)/double(Open+Closed);
173 }
174 
175 template <class PGraph>
176 void GetNodeClustCf(const PGraph& Graph, TIntFltH& NIdCCfH) {
177  TIntTrV NIdCOTriadV;
178  GetTriads(Graph, NIdCOTriadV);
179  NIdCCfH.Clr(false);
180  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
181  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
182  const double CCf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
183  NIdCCfH.AddDat(NIdCOTriadV[i].Val1, CCf);
184  }
185 }
186 
187 template <class PGraph>
188 int64 GetTriads(const PGraph& Graph, int SampleNodes) {
189  int64 OpenTriads, ClosedTriads;
190  return GetTriads(Graph, ClosedTriads, OpenTriads, SampleNodes);
191 }
192 
193 template <class PGraph>
194 int64 GetTriads(const PGraph& Graph, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
195  TIntTrV NIdCOTriadV;
196  GetTriads(Graph, NIdCOTriadV, SampleNodes);
197  uint64 closedTriads = 0;
198  uint64 openTriads = 0;
199  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
200  closedTriads += NIdCOTriadV[i].Val2;
201  openTriads += NIdCOTriadV[i].Val3;
202  }
203  //IAssert(closedTriads/3 < (uint64) TInt::Mx);
204  //IAssert(openTriads < (uint64) TInt::Mx);
205  ClosedTriads = int64(closedTriads/3); // each triad is counted 3 times
206  OpenTriads = int64(openTriads);
207  return ClosedTriads;
208 }
209 
210 // Function pretends that the graph is undirected (count unique connected triples of nodes)
211 template <class PGraph>
212 void GetTriads(const PGraph& Graph, TIntTrV& NIdCOTriadV, int SampleNodes) {
213  const bool IsDir = Graph->HasFlag(gfDirected);
214  TIntSet NbrH;
215  TIntV NIdV;
216  TRnd Rnd(0);
217 
218  Graph->GetNIdV(NIdV);
219  NIdV.Shuffle(Rnd);
220  if (SampleNodes == -1) {
221  SampleNodes = Graph->GetNodes(); }
222  NIdCOTriadV.Clr(false);
223  NIdCOTriadV.Reserve(SampleNodes);
224  for (int node = 0; node < SampleNodes; node++) {
225  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[node]);
226  if (NI.GetDeg() < 2) {
227  NIdCOTriadV.Add(TIntTr(NI.GetId(), 0, 0)); // zero triangles
228  continue;
229  }
230  // find neighborhood
231  NbrH.Clr(false);
232  for (int e = 0; e < NI.GetOutDeg(); e++) {
233  if (NI.GetOutNId(e) != NI.GetId()) {
234  NbrH.AddKey(NI.GetOutNId(e)); }
235  }
236  if (IsDir) {
237  for (int e = 0; e < NI.GetInDeg(); e++) {
238  if (NI.GetInNId(e) != NI.GetId()) {
239  NbrH.AddKey(NI.GetInNId(e)); }
240  }
241  }
242  // count connected neighbors
243  int OpenCnt=0, CloseCnt=0;
244  for (int srcNbr = 0; srcNbr < NbrH.Len(); srcNbr++) {
245  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrH.GetKey(srcNbr));
246  for (int dstNbr = srcNbr+1; dstNbr < NbrH.Len(); dstNbr++) {
247  const int dstNId = NbrH.GetKey(dstNbr);
248  if (SrcNode.IsNbrNId(dstNId)) { CloseCnt++; } // is edge
249  else { OpenCnt++; }
250  }
251  }
252  IAssert(2*(OpenCnt+CloseCnt) == NbrH.Len()*(NbrH.Len()-1));
253  NIdCOTriadV.Add(TIntTr(NI.GetId(), CloseCnt, OpenCnt));
254  }
255 }
256 
257 // Count the number of edges that participate in at least one triad
258 template <class PGraph>
259 int GetTriadEdges(const PGraph& Graph, int SampleEdges) {
260  const bool IsDir = Graph->HasFlag(gfDirected);
261  TIntSet NbrH;
262  int TriadEdges = 0;
263  for(typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
264  NbrH.Clr(false);
265  for (int e = 0; e < NI.GetOutDeg(); e++) {
266  if (NI.GetOutNId(e) != NI.GetId()) {
267  NbrH.AddKey(NI.GetOutNId(e)); }
268  }
269  if (IsDir) {
270  for (int e = 0; e < NI.GetInDeg(); e++) {
271  if (NI.GetInNId(e) != NI.GetId()) {
272  NbrH.AddKey(NI.GetInNId(e)); }
273  }
274  }
275  for (int e = 0; e < NI.GetOutDeg(); e++) {
276  if (!IsDir && NI.GetId()<NI.GetOutNId(e)) { continue; } // for undirected graphs count each edge only once
277  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NI.GetOutNId(e));
278  bool Triad=false;
279  for (int e1 = 0; e1 < SrcNode.GetOutDeg(); e1++) {
280  if (NbrH.IsKey(SrcNode.GetOutNId(e1))) { Triad=true; break; }
281  }
282  if (IsDir && ! Triad) {
283  for (int e1 = 0; e1 < SrcNode.GetInDeg(); e1++) {
284  if (NbrH.IsKey(SrcNode.GetInNId(e1))) { Triad=true; break; }
285  }
286  }
287  if (Triad) { TriadEdges++; }
288  }
289  }
290  return TriadEdges;
291 }
292 
293 // Returns number of undirected triads a node participates in
294 template <class PGraph>
295 int GetNodeTriads(const PGraph& Graph, const int& NId) {
296  int ClosedTriads=0, OpenTriads=0;
297  return GetNodeTriads(Graph, NId, ClosedTriads, OpenTriads);
298 }
299 
300 // Return number of undirected triads a node participates in
301 template <class PGraph>
302 int GetNodeTriads(const PGraph& Graph, const int& NId, int& ClosedTriads, int& OpenTriads) {
303  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
304  ClosedTriads=0; OpenTriads=0;
305  if (NI.GetDeg() < 2) { return 0; }
306  // find neighborhood
307  TIntSet NbrSet(NI.GetDeg());
308  for (int e = 0; e < NI.GetOutDeg(); e++) {
309  if (NI.GetOutNId(e) != NI.GetId()) { // exclude self edges
310  NbrSet.AddKey(NI.GetOutNId(e)); }
311  }
312  if (Graph->HasFlag(gfDirected)) {
313  for (int e = 0; e < NI.GetInDeg(); e++) {
314  if (NI.GetInNId(e) != NI.GetId()) { // exclude self edges
315  NbrSet.AddKey(NI.GetInNId(e)); }
316  }
317  }
318  // count connected neighbors
319  for (int srcNbr = 0; srcNbr < NbrSet.Len(); srcNbr++) {
320  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrSet.GetKey(srcNbr));
321  for (int dstNbr = srcNbr+1; dstNbr < NbrSet.Len(); dstNbr++) {
322  const int dstNId = NbrSet.GetKey(dstNbr);
323  if (SrcNode.IsNbrNId(dstNId)) { ClosedTriads++; }
324  else { OpenTriads++; }
325  }
326  }
327  return ClosedTriads;
328 }
329 
330 // Node NId and a subset of its neighbors GroupSet
331 // InGroupEdges ... triads (NId, g1, g2), where g1 and g2 are in GroupSet
332 // InOutGroupEdges ... triads (NId, g1, o1), where g1 in GroupSet and o1 not in GroupSet
333 // OutGroupEdges ... triads (NId, o1, o2), where o1 and o2 are not in GroupSet
334 template <class PGraph>
335 int GetNodeTriads(const PGraph& Graph, const int& NId, const TIntSet& GroupSet, int& InGroupEdges, int& InOutGroupEdges, int& OutGroupEdges) {
336  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
337  const bool IsDir = Graph->HasFlag(gfDirected);
338  InGroupEdges=0; InOutGroupEdges=0; OutGroupEdges=0;
339  if (NI.GetDeg() < 2) { return 0; }
340  // find neighborhood
341  TIntSet NbrSet(NI.GetDeg());
342  for (int e = 0; e < NI.GetOutDeg(); e++) {
343  if (NI.GetOutNId(e) != NI.GetId()) { // exclude self edges
344  NbrSet.AddKey(NI.GetOutNId(e)); }
345  }
346  if (IsDir) {
347  for (int e = 0; e < NI.GetInDeg(); e++) {
348  if (NI.GetInNId(e) != NI.GetId()) {
349  NbrSet.AddKey(NI.GetInNId(e)); }
350  }
351  }
352  // count connected neighbors
353  for (int srcNbr = 0; srcNbr < NbrSet.Len(); srcNbr++) {
354  const int NbrId = NbrSet.GetKey(srcNbr);
355  const bool NbrIn = GroupSet.IsKey(NbrId);
356  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrId);
357  for (int dstNbr = srcNbr+1; dstNbr < NbrSet.Len(); dstNbr++) {
358  const int DstNId = NbrSet.GetKey(dstNbr);
359  if (SrcNode.IsNbrNId(DstNId)) { // triad (NId, NbrId, DstNid)
360  bool DstIn = GroupSet.IsKey(DstNId);
361  if (NbrIn && DstIn) { InGroupEdges++; }
362  else if (NbrIn || DstIn) { InOutGroupEdges++; }
363  else { OutGroupEdges++; }
364  }
365  }
366  }
367  return InGroupEdges;
368 }
369 
370 // For each node count how many triangles it participates in
371 template <class PGraph>
372 void GetTriadParticip(const PGraph& Graph, TIntPrV& TriadCntV) {
373  TIntH TriadCntH;
374  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
375  const int Triads = GetNodeTriads(Graph, NI.GetId());
376  TriadCntH.AddDat(Triads) += 1;
377  }
378  TriadCntH.GetKeyDatPrV(TriadCntV);
379  TriadCntV.Sort();
380 }
381 
382 template<class PGraph>
383 int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2) {
384  TIntV NbrV;
385  return GetCmnNbrs(Graph, NId1, NId2, NbrV);
386 }
387 
388 // Get common neighbors between a pair of nodes (undirected)
389 template<class PGraph>
390 int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
391  if (! Graph->IsNode(NId1) || ! Graph->IsNode(NId2)) { NbrV.Clr(false); return 0; }
392  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId1);
393  typename PGraph::TObj::TNodeI NI2 = Graph->GetNI(NId2);
394  NbrV.Clr(false);
395  NbrV.Reserve(TMath::Mn(NI1.GetDeg(), NI2.GetDeg()));
396  TIntSet NSet1(NI1.GetDeg()), NSet2(NI2.GetDeg());
397  for (int i = 0; i < NI1.GetDeg(); i++) {
398  const int nid = NI1.GetNbrNId(i);
399  if (nid!=NId1 && nid!=NId2) {
400  NSet1.AddKey(nid); }
401  }
402  for (int i = 0; i < NI2.GetDeg(); i++) {
403  const int nid = NI2.GetNbrNId(i);
404  if (NSet1.IsKey(nid)) {
405  NSet2.AddKey(nid);
406  }
407  }
408  NSet2.GetKeyV(NbrV);
409  return NbrV.Len();
410 }
411 
412 template<>
413 inline int GetCmnNbrs<PUNGraph>(const PUNGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
414  if (! Graph->IsNode(NId1) || ! Graph->IsNode(NId2)) { NbrV.Clr(false); return 0; }
415  const TUNGraph::TNodeI NI1 = Graph->GetNI(NId1);
416  const TUNGraph::TNodeI NI2 = Graph->GetNI(NId2);
417  int i=0, j=0;
418  NbrV.Clr(false);
419  NbrV.Reserve(TMath::Mn(NI1.GetDeg(), NI2.GetDeg()));
420  while (i < NI1.GetDeg() && j < NI2.GetDeg()) {
421  const int nid = NI1.GetNbrNId(i);
422  while (j < NI2.GetDeg() && NI2.GetNbrNId(j) < nid) { j++; }
423  if (j < NI2.GetDeg() && nid==NI2.GetNbrNId(j) && nid!=NId1 && nid!=NId2) {
424  IAssert(NbrV.Empty() || NbrV.Last() < nid);
425  NbrV.Add(nid);
426  j++;
427  }
428  i++;
429  }
430  return NbrV.Len();
431 }
432 
433 // get number of length 2 directed paths between a pair of nodes
434 // for a pair of nodes (i,j): |{u: (i,u) and (u,j) }|
435 template<class PGraph>
436 int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2) {
437  TIntV NbrV;
438  return GetLen2Paths(Graph, NId1, NId2, NbrV);
439 }
440 
441 // get number of length 2 directed paths between a pair of nodes
442 // for a pair of nodes (i,j): {u: (i,u) and (u,j) }
443 template<class PGraph>
444 int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
445  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId1);
446  NbrV.Clr(false);
447  NbrV.Reserve(NI.GetOutDeg());
448  for (int e = 0; e < NI.GetOutDeg(); e++) {
449  const typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(NI.GetOutNId(e));
450  if (MidNI.IsOutNId(NId2)) {
451  NbrV.Add(MidNI.GetId());
452  }
453  }
454  return NbrV.Len();
455 }
456 
457 }; // mamespace TSnap
458 
460 // Node and Edge Network Constraint (by Ron Burt)
461 // works for directed and undirected graphs (but not for multigraphs)
462 template <class PGraph>
463 class TNetConstraint {
464 public:
465  PGraph Graph;
466  THash<TIntPr, TFlt> NodePrCH; // pairs of nodes that have non-zero network constraint
467 public:
468  TNetConstraint(const PGraph& GraphPt, const bool& CalcaAll=true);
469  int Len() const { return NodePrCH.Len(); }
470  double GetC(const int& ConstraintN) const { return NodePrCH[ConstraintN]; }
471  TIntPr GetNodePr(const int& ConstraintN) const { return NodePrCH.GetKey(ConstraintN); }
472  double GetEdgeC(const int& NId1, const int& NId2) const;
473  double GetNodeC(const int& NId) const;
474  void AddConstraint(const int& NId1, const int& NId2);
475  void CalcConstraints();
476  void CalcConstraints(const int& NId);
477  void Dump() const;
478  static void Test();
479 };
480 
481 template <class PGraph>
482 TNetConstraint<PGraph>::TNetConstraint(const PGraph& GraphPt, const bool& CalcaAll) : Graph(GraphPt) {
483  CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph)); // must not be multigraph
484  if (CalcaAll) {
485  CalcConstraints();
486  }
487 }
488 
489 template <class PGraph>
490 double TNetConstraint<PGraph>::GetEdgeC(const int& NId1, const int& NId2) const {
491  if (NodePrCH.IsKey(TIntPr(NId1, NId2))) {
492  return NodePrCH.GetDat(TIntPr(NId1, NId2)); }
493  else {
494  return 0.0; }
495 }
496 
497 template <class PGraph>
498 double TNetConstraint<PGraph>::GetNodeC(const int& NId) const {
499  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId);
500  if (NI1.GetOutDeg() == 0) { return 0.0; }
501  int KeyId = -1;
502  for (int k = 0; k<NI1.GetOutDeg(); k++) {
503  KeyId = NodePrCH.GetKeyId(TIntPr(NI1.GetId(), NI1.GetOutNId(k)));
504  if (KeyId > -1) { break; }
505  }
506  if (KeyId < 0) { return 0.0; }
507  double Constraint = NodePrCH[KeyId];
508  for (int i = KeyId-1; i >-1 && NodePrCH.GetKey(i).Val1()==NId; i--) {
509  Constraint += NodePrCH[i];
510  }
511  for (int i = KeyId+1; i < NodePrCH.Len() && NodePrCH.GetKey(i).Val1()==NId; i++) {
512  Constraint += NodePrCH[i];
513  }
514  return Constraint;
515 }
516 
517 template <class PGraph>
518 void TNetConstraint<PGraph>::AddConstraint(const int& NId1, const int& NId2) {
519  if (NId1==NId2 || NodePrCH.IsKey(TIntPr(NId1, NId2))) {
520  return;
521  }
522  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId1);
523  double Constraint = 0.0;
524  if (NI1.IsOutNId(NId2)) { // is direct edge
525  Constraint += 1.0/(double) NI1.GetOutDeg();
526  }
527  const double SrcC = 1.0/(double) NI1.GetOutDeg();
528  for (int e = 0; e < NI1.GetOutDeg(); e++) {
529  const int MidNId = NI1.GetOutNId(e);
530  if (MidNId == NId1 || MidNId == NId2) { continue; }
531  const typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(MidNId);
532  if (MidNI.IsOutNId(NId2)) {
533  Constraint += SrcC * (1.0/(double)MidNI.GetOutDeg());
534  }
535  }
536  if (Constraint==0) { return; }
537  Constraint = TMath::Sqr(Constraint);
538  NodePrCH.AddDat(TIntPr(NId1, NId2), Constraint);
539 }
540 
541 template <class PGraph>
542 void TNetConstraint<PGraph>::CalcConstraints() {
543  // add edges
544  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
545  AddConstraint(EI.GetSrcNId(), EI.GetDstNId());
546  AddConstraint(EI.GetDstNId(), EI.GetSrcNId());
547  }
548  // add open triads
549  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
550  for (int i = 0; i < NI.GetDeg(); i++) {
551  const int NId1 = NI.GetNbrNId(i);
552  for (int j = 0; j < NI.GetDeg(); j++) {
553  const int NId2 = NI.GetNbrNId(j);
554  AddConstraint(NId1, NId2);
555  }
556  }
557  }
558  NodePrCH.SortByKey();
559 }
560 
561 // calculate constraints around a node id
562 template <class PGraph>
563 void TNetConstraint<PGraph>::CalcConstraints(const int& NId) {
564  typename PGraph::TObj::TNodeI StartNI = Graph->GetNI(NId);
565  TIntSet SeenSet;
566  for (int e = 0; e < StartNI.GetOutDeg(); e++) {
567  typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(StartNI.GetOutNId(e));
568  AddConstraint(NId, MidNI.GetId());
569  for (int i = 0; i < MidNI.GetOutDeg(); i++) {
570  const int EndNId = MidNI.GetOutNId(i);
571  if (! SeenSet.IsKey(EndNId)) {
572  AddConstraint(NId, EndNId);
573  SeenSet.AddKey(EndNId);
574  }
575  }
576  }
577 }
578 
579 template <class PGraph>
580 void TNetConstraint<PGraph>::Dump() const {
581  printf("Edge network constraint: (%d, %d)\n", Graph->GetNodes(), Graph->GetEdges());
582  for (int e = 0; e < NodePrCH.Len(); e++) {
583  printf(" %4d %4d : %f\n", NodePrCH.GetKey(e).Val1(), NodePrCH.GetKey(e).Val2(), NodePrCH[e].Val);
584  }
585  printf("\n");
586 }
587 
588 // example from page 56 of Structural Holes by Ronald S. Burt
589 // (http://www.amazon.com/Structural-Holes-Social-Structure-Competition/dp/0674843711)
590 template <class PGraph>
591 void TNetConstraint<PGraph>::Test() {
592  PUNGraph G = TUNGraph::New();
593  G->AddNode(0); G->AddNode(1); G->AddNode(2); G->AddNode(3);
594  G->AddNode(4); G->AddNode(5); G->AddNode(6);
595  G->AddEdge(0,1); G->AddEdge(0,2); G->AddEdge(0,3); G->AddEdge(0,4); G->AddEdge(0,5); G->AddEdge(0,6);
596  G->AddEdge(1,2); G->AddEdge(1,5); G->AddEdge(1,6);
597  G->AddEdge(2,4);
598  TNetConstraint<PUNGraph> NetConstraint(G, true);
599  // NetConstraint.CalcConstraints(0);
600  NetConstraint.Dump();
601  printf("middle node network constraint: %f\n", NetConstraint.GetNodeC(0));
602 }
603 
THashSet::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1237
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TSnap::GetTriads
int64 GetTriads(const PGraph &Graph, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:194
TNetConstraint::CalcConstraints
void CalcConstraints()
Definition: triad.h:542
TRnd
Definition: dt.h:11
TInt::Val
int Val
Definition: dt.h:1043
TSnap::GetNodeClustCf
double GetNodeClustCf(const PGraph &Graph, const int &NId)
Returns clustering coefficient of a particular node.
Definition: triad.h:168
TNetConstraint::Test
static void Test()
Definition: triad.h:591
TSnap::GetLen2Paths
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:436
TUNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:63
TNetConstraint::Graph
PGraph Graph
Definition: triad.h:465
TSnap::GetCmnNbrs< PUNGraph >
int GetCmnNbrs< PUNGraph >(const PUNGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV)
Definition: triad.h:413
TMath::Sqr
static double Sqr(const double &x)
Definition: xmath.h:12
TNetConstraint::TNetConstraint
TNetConstraint(const PGraph &GraphPt, const bool &CalcaAll=true)
Definition: triad.h:482
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1142
THashSet::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1135
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
gfMultiGraph
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
TUNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:82
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1218
HasGraphFlag
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:38
uint64
unsigned long long uint64
Definition: bd.h:38
TNetConstraint::AddConstraint
void AddConstraint(const int &NId1, const int &NId2)
Definition: triad.h:518
TNetConstraint::GetNodeC
double GetNodeC(const int &NId) const
Definition: triad.h:498
TUNGraph::New
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:149
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1248
TSnap::GetNodeTriads
int GetNodeTriads(const PGraph &Graph, const int &NId)
Returns the number of undirected triads a node NId participates in.
Definition: triad.h:295
TNetConstraint::GetC
double GetC(const int &ConstraintN) const
Definition: triad.h:470
TFltPr
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TUNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:84
TNetConstraint::Dump
void Dump() const
Definition: triad.h:580
gfDirected
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
TNetConstraint::GetEdgeC
double GetEdgeC(const int &NId1, const int &NId2) const
Definition: triad.h:490
CAssert
#define CAssert(Cond)
Definition: bd.h:302
THashSet::Len
int Len() const
Definition: shash.h:1115
int64
long long int64
Definition: bd.h:27
TSnap::GetTriadEdges
int GetTriadEdges(const PGraph &Graph, int SampleEdges=-1)
Counts the number of edges that participate in at least one triad.
Definition: triad.h:259
TVec::Shuffle
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1235
TSnap::GetTriadParticip
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:372
THash::GetKeyDatPrV
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:454
TSnap::GetClustCf
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:100
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TUNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:101
TPair::Val2
TVal2 Val2
Definition: ds.h:35
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:315
TPt
Definition: bd.h:196
TNetConstraint::GetNodePr
TIntPr GetNodePr(const int &ConstraintN) const
Definition: triad.h:471
TIntTr
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:166
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Reserve
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:506
TNetConstraint::NodePrCH
THash< TIntPr, TFlt > NodePrCH
Definition: triad.h:466
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
THash::Len
int Len() const
Definition: hash.h:186
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
TSnap::GetCmnNbrs
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:383
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
TNetConstraint::Len
int Len() const
Definition: triad.h:469