SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
Static Public Member Functions | Static Private Member Functions | List of all members
MotifCluster Class Reference

#include <motifcluster.h>

Static Public Member Functions

static void GetMotifCluster (PNGraph graph, MotifType motif, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
 
static void GetMotifCluster (PUNGraph graph, MotifType motif, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
 
static void MotifAdjacency (PNGraph graph, MotifType motif, WeightVH &weights)
 
static void MotifAdjacency (PUNGraph graph, MotifType motif, WeightVH &weights)
 
static void SpectralCut (const WeightVH &weights, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
 
static double NFiedlerVector (const TSparseColMatrix &W, TFltV &fvec, double tol=kDefaultTol, int maxiter=kMaxIter)
 
static MotifType ParseMotifType (const TStr &motif)
 
static bool IsMotifM1 (PNGraph graph, int u, int v, int w)
 
static bool IsMotifM2 (PNGraph graph, int u, int v, int w)
 
static bool IsMotifM3 (PNGraph graph, int u, int v, int w)
 
static bool IsMotifM4 (PNGraph graph, int u, int v, int w)
 
static bool IsMotifM5 (PNGraph graph, int u, int v, int w)
 
static bool IsMotifM6 (PNGraph graph, int u, int v, int w)
 
static bool IsMotifM7 (PNGraph graph, int u, int v, int w)
 
static bool IsMotifM8 (PNGraph graph, int center, int v, int w)
 
static bool IsMotifM9 (PNGraph graph, int center, int v, int w)
 
static bool IsMotifM10 (PNGraph graph, int center, int v, int w)
 
static bool IsMotifM11 (PNGraph graph, int center, int v, int w)
 
static bool IsMotifM12 (PNGraph graph, int center, int v, int w)
 
static bool IsMotifM13 (PNGraph graph, int center, int v, int w)
 
static bool IsUnidirEdge (PNGraph graph, int u, int v)
 
static bool IsBidirEdge (PNGraph graph, int u, int v)
 
static bool IsNoEdge (PNGraph graph, int u, int v)
 
static void DegreeOrdering (PNGraph graph, TIntV &order)
 

Static Private Member Functions

static void EdgeMotifAdjacency (PNGraph graph, WeightVH &weights)
 
static void EdgeMotifAdjacency (PUNGraph graph, WeightVH &weights)
 
static void TriangleMotifAdjacency (PNGraph graph, MotifType motif, WeightVH &weights)
 
static void WedgeMotifAdjacency (PNGraph graph, MotifType motif, WeightVH &weights)
 
static void BifanMotifAdjacency (PNGraph graph, WeightVH &weights)
 
static void SemicliqueMotifAdjacency (PUNGraph graph, WeightVH &weights)
 
static void CliqueMotifAdjacency (PUNGraph graph, int clique_size, WeightVH &weights)
 

Detailed Description

Definition at line 56 of file motifcluster.h.

Member Function Documentation

void MotifCluster::BifanMotifAdjacency ( PNGraph  graph,
WeightVH &  weights 
)
staticprivate

Definition at line 341 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::BegI(), TNGraph::BegNI(), THash< TKey, TDat, THashFunc >::EndI(), TNGraph::EndNI(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), IncrementWeight(), IsNoEdge(), IsUnidirEdge(), and TVec< TVal, TSizeTy >::Len().

Referenced by MotifAdjacency().

341  {
342  // Find all pairs of nodes that are not adjacent
343  // Note: does not scale to large sparse networks but will work for smaller
344  // networks such as common neuronal connectivity datasets.
345  TIntV node_ids;
346  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
347  node_ids.Add(NI.GetId());
348  }
349  for (int i = 0; i < node_ids.Len(); i++) {
350  for (int j = i + 1; j < node_ids.Len(); j++) {
351  int src1 = node_ids[i];
352  int src2 = node_ids[j];
353  if (IsNoEdge(graph, src1, src2)) {
354  // All unidirectional out-neighbors of src1
355  THash<TInt, TInt> nbr_counts;
356  TNGraph::TNodeI NI1 = graph->GetNI(src1);
357  for (int k = 0; k < NI1.GetOutDeg(); k++) {
358  int nbr = NI1.GetOutNId(k);
359  if (IsUnidirEdge(graph, src1, nbr)) {
360  nbr_counts(nbr) += 1;
361  }
362  }
363 
364  // All unidirectional out-neighbors of src2
365  TNGraph::TNodeI NI2 = graph->GetNI(src2);
366  for (int k = 0; k < NI2.GetOutDeg(); k++) {
367  int nbr = NI2.GetOutNId(k);
368  if (IsUnidirEdge(graph, src2, nbr)) {
369  nbr_counts(nbr) += 1;
370  }
371  }
372 
373  // Get all common outgoing neighbors
374  TIntV common;
375  for (THash<TInt, TInt>::TIter it = nbr_counts.BegI();
376  it < nbr_counts.EndI(); it++) {
377  if (it->Dat == 2) {
378  common.Add(it->Key);
379  }
380  }
381 
382  // Update weights with all common neighbors
383  for (int ind1 = 0; ind1 < common.Len(); ind1++) {
384  for (int ind2 = (ind1 + 1); ind2 < common.Len(); ind2++) {
385  int dst1 = common[ind1];
386  int dst2 = common[ind2];
387  if (IsNoEdge(graph, dst1, dst2)) {
388  IncrementWeight(src1, src2, weights);
389  IncrementWeight(src1, dst1, weights);
390  IncrementWeight(src1, dst2, weights);
391  IncrementWeight(src2, dst1, weights);
392  IncrementWeight(src2, dst2, weights);
393  IncrementWeight(dst1, dst2, weights);
394  }
395  }
396  }
397  }
398  }
399  }
400 }
THash::BegI
TIter BegI() const
Definition: hash.h:213
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::EndI
TIter EndI() const
Definition: hash.h:218
IncrementWeight
static void IncrementWeight(int i, int j, WeightVH &weights)
Definition: motifcluster.cpp:29
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TNGraph::TNodeI::GetOutNId
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
MotifCluster::IsNoEdge
static bool IsNoEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::CliqueMotifAdjacency ( PUNGraph  graph,
int  clique_size,
WeightVH &  weights 
)
staticprivate

Definition at line 503 of file motifcluster.cpp.

References ChibaNishizekiWeighter::Run(), and ChibaNishizekiWeighter::weights().

Referenced by MotifAdjacency().

504  {
505  ChibaNishizekiWeighter cnw(graph);
506  cnw.Run(clique_size);
507  weights = cnw.weights();
508 }

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::DegreeOrdering ( PNGraph  graph,
TIntV &  order 
)
static

Definition at line 185 of file motifcluster.cpp.

References TNGraph::BegNI(), TNGraph::EndNI(), TNGraph::GetMxNId(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::PutAll(), and TVec< TVal, TSizeTy >::Sort().

Referenced by TriangleMotifAdjacency().

185  {
186  // Note: This is the most efficient when the nodes are numbered
187  // 0, 1, ..., num_nodes - 1.
188  int max_nodes = graph->GetMxNId() + 1;
189  TVec< TKeyDat<TInt, TInt> > degrees(max_nodes);
190  degrees.PutAll(TKeyDat<TInt, TInt>(0, 0));
191  // Set the degree of a node to be the number of nodes adjacent to the node in
192  // the undirected graph.
193  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
194  int src = NI.GetId();
195  int num_nbrs = NI.GetOutDeg();
196  // For each incoming edge that is not an outgoing edge, include it.
197  for (int i = 0; i < NI.GetInDeg(); ++i) {
198  int dst = NI.GetInNId(i);
199  if (!NI.IsOutNId(dst)) {
200  ++num_nbrs;
201  }
202  }
203  degrees[src] = TKeyDat<TInt, TInt>(num_nbrs, src);
204  }
205 
206  degrees.Sort();
207  order = TIntV(max_nodes);
208  for (int i = 0; i < order.Len(); ++i) {
209  order[degrees[i].Dat] = i;
210  }
211 }
TKeyDat
Definition: ds.h:346
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TIntV
TVec< TInt > TIntV
Definition: ds.h:1594
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::EdgeMotifAdjacency ( PNGraph  graph,
WeightVH &  weights 
)
staticprivate

Definition at line 443 of file motifcluster.cpp.

References TNGraph::BegEI(), TNGraph::EndEI(), IncrementWeight(), and TNGraph::IsEdge().

Referenced by MotifAdjacency().

443  {
444  for (TNGraph::TEdgeI it = graph->BegEI(); it < graph->EndEI(); it++) {
445  int src = it.GetSrcNId();
446  int dst = it.GetDstNId();
447  if (src == dst) {
448  continue;
449  }
450  // Only count reciprocated edges if src < dst
451  if (!graph->IsEdge(dst, src) || src < dst) {
452  IncrementWeight(src, dst, weights);
453  }
454  }
455 }
TNGraph::TEdgeI
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
IncrementWeight
static void IncrementWeight(int i, int j, WeightVH &weights)
Definition: motifcluster.cpp:29

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::EdgeMotifAdjacency ( PUNGraph  graph,
WeightVH &  weights 
)
staticprivate

Definition at line 457 of file motifcluster.cpp.

References TUNGraph::BegEI(), TUNGraph::EndEI(), and IncrementWeight().

457  {
458  for (TUNGraph::TEdgeI it = graph->BegEI(); it < graph->EndEI(); it++) {
459  int src = it.GetSrcNId();
460  int dst = it.GetDstNId();
461  if (src == dst) {
462  continue;
463  }
464  IncrementWeight(src, dst, weights);
465  }
466 }
TUNGraph::TEdgeI
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
IncrementWeight
static void IncrementWeight(int i, int j, WeightVH &weights)
Definition: motifcluster.cpp:29

Here is the call graph for this function:

void MotifCluster::GetMotifCluster ( PNGraph  graph,
MotifType  motif,
TSweepCut &  sweepcut,
double  tol = kDefaultTol,
int  maxiter = kMaxIter 
)
static

Definition at line 701 of file motifcluster.cpp.

References MotifAdjacency(), and SpectralCut().

703  {
704  WeightVH weights;
705  MotifAdjacency(graph, motif, weights);
706  SpectralCut(weights, sweepcut, tol, maxiter);
707 }
MotifCluster::SpectralCut
static void SpectralCut(const WeightVH &weights, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
Definition: motifcluster.cpp:871
MotifCluster::MotifAdjacency
static void MotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
Definition: motifcluster.cpp:471

Here is the call graph for this function:

void MotifCluster::GetMotifCluster ( PUNGraph  graph,
MotifType  motif,
TSweepCut &  sweepcut,
double  tol = kDefaultTol,
int  maxiter = kMaxIter 
)
static

Definition at line 709 of file motifcluster.cpp.

References MotifAdjacency(), and SpectralCut().

711  {
712  WeightVH weights;
713  MotifAdjacency(graph, motif, weights);
714  SpectralCut(weights, sweepcut, tol, maxiter);
715 }
MotifCluster::SpectralCut
static void SpectralCut(const WeightVH &weights, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
Definition: motifcluster.cpp:871
MotifCluster::MotifAdjacency
static void MotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
Definition: motifcluster.cpp:471

Here is the call graph for this function:

bool MotifCluster::IsBidirEdge ( PNGraph  graph,
int  u,
int  v 
)
static

Definition at line 80 of file motifcluster.cpp.

References TNGraph::IsEdge().

Referenced by IsMotifM11(), IsMotifM12(), IsMotifM13(), IsMotifM2(), IsMotifM3(), IsMotifM4(), IsMotifM6(), and IsMotifM7().

80  {
81  return graph->IsEdge(u, v) && graph->IsEdge(v, u);
82 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM1 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 84 of file motifcluster.cpp.

References IsUnidirEdge().

Referenced by TriangleMotifAdjacency().

84  {
85  return ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, v, w) &&
86  IsUnidirEdge(graph, w, u)) ||
87  (IsUnidirEdge(graph, u, w) && IsUnidirEdge(graph, w, v) &&
88  IsUnidirEdge(graph, v, u)));
89 }
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM10 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 160 of file motifcluster.cpp.

References IsNoEdge(), and IsUnidirEdge().

Referenced by WedgeMotifAdjacency().

160  {
161  return IsNoEdge(graph, v, w) && IsUnidirEdge(graph, v, center) &&
162  IsUnidirEdge(graph, w, center);
163 }
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76
MotifCluster::IsNoEdge
static bool IsNoEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM11 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 165 of file motifcluster.cpp.

References IsBidirEdge(), IsNoEdge(), and IsUnidirEdge().

Referenced by WedgeMotifAdjacency().

165  {
166  return IsNoEdge(graph, v, w) &&
167  ((IsBidirEdge(graph, center, v) && IsUnidirEdge(graph, center, w)) ||
168  (IsBidirEdge(graph, center, w) && IsUnidirEdge(graph, center, v)));
169 }
MotifCluster::IsBidirEdge
static bool IsBidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:80
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76
MotifCluster::IsNoEdge
static bool IsNoEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM12 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 171 of file motifcluster.cpp.

References IsBidirEdge(), IsNoEdge(), and IsUnidirEdge().

Referenced by WedgeMotifAdjacency().

171  {
172  return IsNoEdge(graph, v, w) &&
173  ((IsBidirEdge(graph, center, v) && IsUnidirEdge(graph, w, center)) ||
174  (IsBidirEdge(graph, center, w) && IsUnidirEdge(graph, v, center)));
175 }
MotifCluster::IsBidirEdge
static bool IsBidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:80
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76
MotifCluster::IsNoEdge
static bool IsNoEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM13 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 177 of file motifcluster.cpp.

References IsBidirEdge(), and IsNoEdge().

Referenced by WedgeMotifAdjacency().

177  {
178  return IsNoEdge(graph, v, w) && IsBidirEdge(graph, center, v)
179  && IsBidirEdge(graph, center, w);
180 }
MotifCluster::IsBidirEdge
static bool IsBidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:80
MotifCluster::IsNoEdge
static bool IsNoEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM2 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 91 of file motifcluster.cpp.

References IsBidirEdge(), and IsUnidirEdge().

Referenced by TriangleMotifAdjacency().

91  {
92  return ((IsBidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w) &&
93  IsUnidirEdge(graph, w, v)) ||
94  (IsBidirEdge(graph, u, v) && IsUnidirEdge(graph, w, u) &&
95  IsUnidirEdge(graph, v, w)) ||
96  (IsBidirEdge(graph, u, w) && IsUnidirEdge(graph, u, v) &&
97  IsUnidirEdge(graph, v, w)) ||
98  (IsBidirEdge(graph, u, w) && IsUnidirEdge(graph, v, u) &&
99  IsUnidirEdge(graph, w, v)) ||
100  (IsBidirEdge(graph, v, w) && IsUnidirEdge(graph, v, u) &&
101  IsUnidirEdge(graph, u, w)) ||
102  (IsBidirEdge(graph, v, w) && IsUnidirEdge(graph, u, v) &&
103  IsUnidirEdge(graph, w, u)));
104 }
MotifCluster::IsBidirEdge
static bool IsBidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:80
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM3 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 106 of file motifcluster.cpp.

References IsBidirEdge(), and IsUnidirEdge().

Referenced by TriangleMotifAdjacency().

106  {
107  if ((IsBidirEdge( graph, u, v) && IsBidirEdge( graph, v, w)) &&
108  (IsUnidirEdge(graph, u, w) || IsUnidirEdge(graph, w, u))) { return true; }
109  if ((IsBidirEdge( graph, u, w) && IsBidirEdge( graph, w, v)) &&
110  (IsUnidirEdge(graph, u, v) || IsUnidirEdge(graph, v, u))) { return true; }
111  if ((IsBidirEdge( graph, w, u) && IsBidirEdge( graph, u, v)) &&
112  (IsUnidirEdge(graph, w, v) || IsUnidirEdge(graph, v, w))) { return true; }
113  return false;
114 }
MotifCluster::IsBidirEdge
static bool IsBidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:80
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM4 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 116 of file motifcluster.cpp.

References IsBidirEdge().

Referenced by TriangleMotifAdjacency().

116  {
117  return IsBidirEdge(graph, u, v) && IsBidirEdge(graph, u, w) &&
118  IsBidirEdge(graph, v, w);
119 }
MotifCluster::IsBidirEdge
static bool IsBidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:80

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM5 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 121 of file motifcluster.cpp.

References IsUnidirEdge().

Referenced by TriangleMotifAdjacency().

121  {
122  if ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w)) &&
123  (IsUnidirEdge(graph, v, w) || IsUnidirEdge(graph, w, v))) { return true; }
124  if ((IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, v, w)) &&
125  (IsUnidirEdge(graph, u, w) || IsUnidirEdge(graph, w, u))) { return true; }
126  if ((IsUnidirEdge(graph, w, v) && IsUnidirEdge(graph, w, u)) &&
127  (IsUnidirEdge(graph, v, u) || IsUnidirEdge(graph, u, v))) { return true; }
128  return false;
129 }
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM6 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 131 of file motifcluster.cpp.

References IsBidirEdge(), and IsUnidirEdge().

Referenced by TriangleMotifAdjacency().

131  {
132  return ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w) &&
133  IsBidirEdge(graph, v, w)) ||
134  (IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, v, w) &&
135  IsBidirEdge(graph, u, w)) ||
136  (IsUnidirEdge(graph, w, u) && IsUnidirEdge(graph, w, v) &&
137  IsBidirEdge(graph, u, v)));
138 }
MotifCluster::IsBidirEdge
static bool IsBidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:80
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM7 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 140 of file motifcluster.cpp.

References IsBidirEdge(), and IsUnidirEdge().

Referenced by TriangleMotifAdjacency().

140  {
141  return ((IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, w, u) &&
142  IsBidirEdge(graph, v, w)) ||
143  (IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, w, v) &&
144  IsBidirEdge(graph, u, w)) ||
145  (IsUnidirEdge(graph, u, w) && IsUnidirEdge(graph, v, w) &&
146  IsBidirEdge(graph, u, v)));
147 }
MotifCluster::IsBidirEdge
static bool IsBidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:80
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM8 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 149 of file motifcluster.cpp.

References IsNoEdge(), and IsUnidirEdge().

Referenced by WedgeMotifAdjacency().

149  {
150  return IsNoEdge(graph, v, w) && IsUnidirEdge(graph, center, v) &&
151  IsUnidirEdge(graph, center, w);
152 }
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76
MotifCluster::IsNoEdge
static bool IsNoEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsMotifM9 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 154 of file motifcluster.cpp.

References IsNoEdge(), and IsUnidirEdge().

Referenced by WedgeMotifAdjacency().

154  {
155  return IsNoEdge(graph, v, w) &&
156  ((IsUnidirEdge(graph, center, v) && IsUnidirEdge(graph, w, center)) ||
157  (IsUnidirEdge(graph, center, w) && IsUnidirEdge(graph, v, center)));
158 }
MotifCluster::IsUnidirEdge
static bool IsUnidirEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:76
MotifCluster::IsNoEdge
static bool IsNoEdge(PNGraph graph, int u, int v)
Definition: motifcluster.cpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsNoEdge ( PNGraph  graph,
int  u,
int  v 
)
static

Definition at line 72 of file motifcluster.cpp.

References TNGraph::IsEdge().

Referenced by BifanMotifAdjacency(), IsMotifM10(), IsMotifM11(), IsMotifM12(), IsMotifM13(), IsMotifM8(), and IsMotifM9().

72  {
73  return !graph->IsEdge(u, v) && !graph->IsEdge(v, u);
74 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool MotifCluster::IsUnidirEdge ( PNGraph  graph,
int  u,
int  v 
)
static

Definition at line 76 of file motifcluster.cpp.

References TNGraph::IsEdge().

Referenced by BifanMotifAdjacency(), IsMotifM1(), IsMotifM10(), IsMotifM11(), IsMotifM12(), IsMotifM2(), IsMotifM3(), IsMotifM5(), IsMotifM6(), IsMotifM7(), IsMotifM8(), and IsMotifM9().

76  {
77  return graph->IsEdge(u, v) && !graph->IsEdge(v, u);
78 }

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::MotifAdjacency ( PNGraph  graph,
MotifType  motif,
WeightVH &  weights 
)
static

Definition at line 471 of file motifcluster.cpp.

References bifan, BifanMotifAdjacency(), edge, EdgeMotifAdjacency(), TNGraph::GetMxNId(), M1, M10, M11, M12, M13, M2, M3, M4, M5, M6, M7, M8, M9, TExcept::Throw(), TriangleMotifAdjacency(), and WedgeMotifAdjacency().

Referenced by GetMotifCluster().

472  {
473  weights = WeightVH(graph->GetMxNId() + 1);
474  switch (motif) {
475  case M1:
476  case M2:
477  case M3:
478  case M4:
479  case M5:
480  case M6:
481  case M7:
482  TriangleMotifAdjacency(graph, motif, weights);
483  break;
484  case M8:
485  case M9:
486  case M10:
487  case M11:
488  case M12:
489  case M13:
490  WedgeMotifAdjacency(graph, motif, weights);
491  break;
492  case bifan:
493  BifanMotifAdjacency(graph, weights);
494  break;
495  case edge:
496  EdgeMotifAdjacency(graph, weights);
497  break;
498  default:
499  TExcept::Throw("Unknown directed motif type");
500  }
501 }
TExcept::Throw
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
WeightVH
TVec< THash< TInt, TFlt > > WeightVH
Definition: localmotifcluster.h:6
MotifCluster::WedgeMotifAdjacency
static void WedgeMotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
Definition: motifcluster.cpp:282
MotifCluster::BifanMotifAdjacency
static void BifanMotifAdjacency(PNGraph graph, WeightVH &weights)
Definition: motifcluster.cpp:341
MotifCluster::TriangleMotifAdjacency
static void TriangleMotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
Definition: motifcluster.cpp:213
MotifCluster::EdgeMotifAdjacency
static void EdgeMotifAdjacency(PNGraph graph, WeightVH &weights)
Definition: motifcluster.cpp:443

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::MotifAdjacency ( PUNGraph  graph,
MotifType  motif,
WeightVH &  weights 
)
static

Definition at line 510 of file motifcluster.cpp.

References clique3, clique4, clique5, clique6, clique7, clique8, clique9, CliqueMotifAdjacency(), edge, EdgeMotifAdjacency(), TUNGraph::GetMxNId(), semiclique, SemicliqueMotifAdjacency(), TExcept::Throw(), and triangle.

511  {
512  weights = WeightVH(graph->GetMxNId() + 1);
513  switch (motif) {
514  case triangle:
515  case clique3:
516  CliqueMotifAdjacency(graph, 3, weights);
517  break;
518  case clique4:
519  CliqueMotifAdjacency(graph, 4, weights);
520  break;
521  case clique5:
522  CliqueMotifAdjacency(graph, 5, weights);
523  break;
524  case clique6:
525  CliqueMotifAdjacency(graph, 6, weights);
526  break;
527  case clique7:
528  CliqueMotifAdjacency(graph, 7, weights);
529  break;
530  case clique8:
531  CliqueMotifAdjacency(graph, 8, weights);
532  break;
533  case clique9:
534  CliqueMotifAdjacency(graph, 9, weights);
535  break;
536  case semiclique:
537  SemicliqueMotifAdjacency(graph, weights);
538  break;
539  case edge:
540  EdgeMotifAdjacency(graph, weights);
541  default:
542  TExcept::Throw("Unknown undirected motif type");
543  }
544 }
TExcept::Throw
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
WeightVH
TVec< THash< TInt, TFlt > > WeightVH
Definition: localmotifcluster.h:6
MotifCluster::SemicliqueMotifAdjacency
static void SemicliqueMotifAdjacency(PUNGraph graph, WeightVH &weights)
Definition: motifcluster.cpp:405
MotifCluster::CliqueMotifAdjacency
static void CliqueMotifAdjacency(PUNGraph graph, int clique_size, WeightVH &weights)
Definition: motifcluster.cpp:503
MotifCluster::EdgeMotifAdjacency
static void EdgeMotifAdjacency(PNGraph graph, WeightVH &weights)
Definition: motifcluster.cpp:443

Here is the call graph for this function:

double MotifCluster::NFiedlerVector ( const TSparseColMatrix &  W,
TFltV &  fvec,
double  tol = kDefaultTol,
int  maxiter = kMaxIter 
)
static

Definition at line 717 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), TSparseColMatrix::ColSpVV, TFullColMatrix::ColV, TMatrix::GetCols(), TMatrix::GetRows(), TVec< TVal, TSizeTy >::Len(), TMatrix::Multiply(), TLinAlg::Normalize(), TVec< TVal, TSizeTy >::PutAll(), TMath::Sqrt(), SymeigsSmallest(), and TExcept::Throw().

Referenced by SpectralCut().

718  {
719  if (W.GetRows() != W.GetCols()) {
720  TExcept::Throw("Matrix must be square.");
721  }
722 
723  int N = W.GetCols();
724 
725  // all ones vector
726  TFltV e(N);
727  e.PutAll(1.0);
728  // degree vector
729  TFltV d(N);
730  d.PutAll(0.0);
731  W.Multiply(e, d);
732 
733  // Unit first eigenvector and d^{-1/2}
734  TFltV v0(N);
735  TFltV dnorm(N);
736  for (int i = 0; i < d.Len(); i++) {
737  if (d[i] <= 0.0) {
738  TExcept::Throw("Node with zero degree.");
739  }
740  v0[i] = TMath::Sqrt(d[i]);
741  dnorm[i] = 1.0 / TMath::Sqrt(d[i]);
742  }
743  TLinAlg::Normalize(v0);
744 
745  // Form I + Ln, where Ln is normalized Laplacian
746  TVec< TIntFltKdV > L_weights(N);
747  for (int j = 0; j < N; j++) {
748  const TIntFltKdV& W_col = W.ColSpVV[j];
749  TIntFltKdV& L_col = L_weights[j];
750  for (int ind = 0; ind < W_col.Len(); ind++) {
751  int i = W_col[ind].Key;
752  double val = W_col[ind].Dat;
753  L_col.Add(TIntFltKd(i, -val * dnorm[i] * dnorm[j]));
754  }
755  L_col.Add(TIntFltKd(j, 2.0));
756  }
757 
758  TSparseColMatrix L(L_weights, N, N);
759  TFltV evals;
760  TFullColMatrix evecs;
761  SymeigsSmallest(L, 2, evals, evecs, tol, maxiter);
762  fvec = evecs.ColV[1];
763  for (int i = 0; i < fvec.Len(); i++) {
764  fvec[i] *= dnorm[i];
765  }
766  // Adjust by 1 on the eigenvalue since we added the identity
767  return evals[1] - 1;
768 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntFltKd
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:381
TMath::Sqrt
static double Sqrt(const double &x)
Definition: xmath.h:13
TLinAlg::Normalize
static void Normalize(TFltV &x)
Definition: linalg.cpp:328
TExcept::Throw
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
TMatrix::GetRows
int GetRows() const
Definition: linalg.h:45
TMatrix::GetCols
int GetCols() const
Definition: linalg.h:47
SymeigsSmallest
void SymeigsSmallest(const TSparseColMatrix &A, int nev, TFltV &evals, TFullColMatrix &evecs, double tol, int maxiter)
Definition: motifcluster.cpp:955
TSparseColMatrix::ColSpVV
TVec< TIntFltKdV > ColSpVV
Definition: linalg.h:60
TMatrix::Multiply
void Multiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.h:24
TFullColMatrix::ColV
TVec< TFltV > ColV
Definition: linalg.h:131
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

MotifType MotifCluster::ParseMotifType ( const TStr &  motif)
static

Definition at line 36 of file motifcluster.cpp.

References bifan, clique3, clique4, clique5, clique6, clique7, clique8, clique9, edge, TStr::GetLc(), M1, M10, M11, M12, M13, M2, M3, M4, M5, M6, M7, M8, M9, semiclique, TExcept::Throw(), and triangle.

36  {
37  TStr motif_lc = motif.GetLc();
38  if (motif_lc == "m1") { return M1; }
39  else if (motif_lc == "m2") { return M2; }
40  else if (motif_lc == "m3") { return M3; }
41  else if (motif_lc == "m4") { return M4; }
42  else if (motif_lc == "m5") { return M5; }
43  else if (motif_lc == "m6") { return M6; }
44  else if (motif_lc == "m7") { return M7; }
45  else if (motif_lc == "m8") { return M8; }
46  else if (motif_lc == "m9") { return M9; }
47  else if (motif_lc == "m10") { return M10; }
48  else if (motif_lc == "m11") { return M11; }
49  else if (motif_lc == "m12") { return M12; }
50  else if (motif_lc == "m13") { return M13; }
51  else if (motif_lc == "bifan") { return bifan; }
52  else if (motif_lc == "bi-fan") { return bifan; }
53  else if (motif_lc == "triangle") { return triangle; }
54  else if (motif_lc == "clique3") { return clique3; }
55  else if (motif_lc == "clique4") { return clique4; }
56  else if (motif_lc == "clique5") { return clique5; }
57  else if (motif_lc == "clique6") { return clique6; }
58  else if (motif_lc == "clique7") { return clique7; }
59  else if (motif_lc == "clique8") { return clique8; }
60  else if (motif_lc == "clique9") { return clique9; }
61  else if (motif_lc == "semiclique") { return semiclique; }
62  else if (motif_lc == "semi-clique") { return semiclique; }
63  else if (motif_lc == "edge") { return edge; }
64  else if (motif_lc == "undir") { return edge; }
65  else if (motif_lc == "undirected") { return edge; }
66  else { TExcept::Throw("Unknown motif"); }
67  return edge;
68 }
TExcept::Throw
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
TStr::GetLc
TStr GetLc() const
Definition: dt.h:502
TStr
Definition: dt.h:412

Here is the call graph for this function:

void MotifCluster::SemicliqueMotifAdjacency ( PUNGraph  graph,
WeightVH &  weights 
)
staticprivate

Definition at line 405 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), TUNGraph::BegNI(), TUNGraph::EndNI(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), TUNGraph::TNodeI::GetOutDeg(), IncrementWeight(), TUNGraph::IsEdge(), and TVec< TVal, TSizeTy >::Len().

Referenced by MotifAdjacency().

405  {
406  for (TUNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
407  int src = NI.GetId();
408  for (int j = 0; j < NI.GetDeg(); j++) {
409  int dst = NI.GetNbrNId(j);
410  if (dst <= src) { continue; }
411 
412  // Common neighbors of dst that are neighbors of src
413  TIntV common;
414  TUNGraph::TNodeI dst_NI = graph->GetNI(dst);
415  for (int k = 0; k < dst_NI.GetOutDeg(); k++) {
416  int nbr = dst_NI.GetNbrNId(k);
417  if (nbr != src && nbr != dst && NI.IsNbrNId(nbr)) {
418  common.Add(nbr);
419  }
420  }
421 
422  for (int k = 0; k < common.Len(); k++) {
423  for (int l = k + 1; l < common.Len(); l++) {
424  int nbr1 = common[k];
425  int nbr2 = common[l];
426  if (!graph->IsEdge(nbr1, nbr2)) {
427  IncrementWeight(src, dst, weights);
428  IncrementWeight(src, nbr1, weights);
429  IncrementWeight(src, nbr2, weights);
430  IncrementWeight(dst, nbr1, weights);
431  IncrementWeight(dst, nbr2, weights);
432  IncrementWeight(nbr1, nbr2, weights);
433  }
434  }
435  }
436  }
437  }
438 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TUNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:94
IncrementWeight
static void IncrementWeight(int i, int j, WeightVH &weights)
Definition: motifcluster.cpp:29
TUNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:111
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::SpectralCut ( const WeightVH &  weights,
TSweepCut &  sweepcut,
double  tol = kDefaultTol,
int  maxiter = kMaxIter 
)
static

Definition at line 871 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::BegI(), TSweepCut::cluster, TSweepCut::component, TSweepCut::cond, TSweepCut::eig, THash< TKey, TDat, THashFunc >::EndI(), TSnap::GetWccs(), TCnCom::IsNIdIn(), TCnCom::Len(), TVec< TVal, TSizeTy >::Len(), MapIdsToFirstN(), NFiedlerVector(), TCnCom::NIdV, Sweep(), TSweepCut::sweep_profile, and UnweightedGraphRepresentation().

Referenced by GetMotifCluster().

872  {
873  // Form graph and get maximum component
874  PUNGraph graph = UnweightedGraphRepresentation(weights);
875  TCnComV components;
876  TSnap::GetWccs(graph, components);
877  int max_wcc_size = 0;
878  int max_wcc_ind = -1;
879  for (int i = 0; i < components.Len(); i++) {
880  int size = components[i].Len();
881  if (size > max_wcc_size) {
882  max_wcc_size = size;
883  max_wcc_ind = i;
884  }
885  }
886  TCnCom comp = components[max_wcc_ind];
887  sweepcut.component = comp;
888  if (comp.Len() == 1) {
889  printf("WARNING: No non-trivial connected components "
890  "(likely due to no instances of the motif)\n");
891  sweepcut.cond = 0;
892  sweepcut.eig = 0;
893  return;
894  }
895 
896 
897  // Map largest connected component to a matrix, keeping track of ids.
898  THash<TInt, TInt> id_map;
899  TIntV rev_id_map;
900  MapIdsToFirstN(comp.NIdV, id_map, rev_id_map);
901 
902  TVec<TIntFltKdV> matrix_entries(comp.Len());
903  for (int ind1 = 0; ind1 < comp.Len(); ++ind1) {
904  int c_ind = comp[ind1];
905  const THash<TInt, TInt>& edge_list = weights[c_ind];
906  int i_ind = id_map(c_ind);
907  TIntFltKdV& col = matrix_entries[i_ind];
908  for (THash<TInt, TInt>::TIter it = edge_list.BegI(); it < edge_list.EndI();
909  it++) {
910  int ind2 = it->Key;
911  int val = it->Dat;
912  if (comp.IsNIdIn(ind2)) {
913  int j_ind = id_map(ind2);
914  col.Add(TIntFltKd(j_ind, val));
915  // Add symmetric part
916  matrix_entries[j_ind].Add(TIntFltKd(i_ind, val));
917  }
918  }
919  }
920 
921  // Get Fiedler vector and run the sweep
922  TSparseColMatrix W(matrix_entries, comp.Len(), comp.Len());
923  TFltV fvec;
924  sweepcut.eig = NFiedlerVector(W, fvec, tol, maxiter);
925 
926  TFltV conds;
927  TIntV order;
928  Sweep(W, fvec, conds, order);
929  sweepcut.sweep_profile = conds;
930 
931  // Extract the cluster
932  double min_cond = 2.0;
933  int min_ind = -1;
934  for (int i = 0; i < conds.Len(); i++) {
935  double cond = conds[i];
936  if (cond < min_cond) {
937  min_cond = cond;
938  min_ind = i;
939  }
940  }
941  sweepcut.cond = min_cond;
942  TIntV cluster;
943  int start = 0;
944  int end = min_ind + 1;
945  if (end >= conds.Len() / 2) {
946  start = min_ind + 1;
947  end = conds.Len() + 1;
948  }
949  for (int i = start; i < end; i++) {
950  cluster.Add(rev_id_map[order[i]]);
951  }
952  sweepcut.cluster = cluster;
953 }
THash::BegI
TIter BegI() const
Definition: hash.h:213
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntFltKd
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:381
TSweepCut::cluster
TIntV cluster
Definition: motifcluster.h:40
THash::EndI
TIter EndI() const
Definition: hash.h:218
TSweepCut::eig
double eig
Definition: motifcluster.h:42
TSweepCut::component
TCnCom component
Definition: motifcluster.h:44
TCnCom
Definition: cncom.h:88
TCnCom::NIdV
TIntV NIdV
Definition: cncom.h:90
UnweightedGraphRepresentation
static PUNGraph UnweightedGraphRepresentation(const WeightVH &weights)
Definition: motifcluster.cpp:772
TCnCom::IsNIdIn
bool IsNIdIn(const int &NId) const
Definition: cncom.h:110
TSweepCut::cond
double cond
Definition: motifcluster.h:41
TSweepCut::sweep_profile
TFltV sweep_profile
Definition: motifcluster.h:43
MotifCluster::NFiedlerVector
static double NFiedlerVector(const TSparseColMatrix &W, TFltV &fvec, double tol=kDefaultTol, int maxiter=kMaxIter)
Definition: motifcluster.cpp:717
MapIdsToFirstN
static void MapIdsToFirstN(const TIntV &ids, THash< TInt, TInt > &id_map, TIntV &rev_id_map)
Definition: motifcluster.cpp:796
TCnCom::Len
int Len() const
Definition: cncom.h:101
TPt
Definition: bd.h:196
Sweep
static void Sweep(const TSparseColMatrix &W, const TFltV &fvec, TFltV &conds, TIntV &order)
Definition: motifcluster.cpp:813
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TSnap::GetWccs
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::TriangleMotifAdjacency ( PNGraph  graph,
MotifType  motif,
WeightVH &  weights 
)
staticprivate

Definition at line 213 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegNI(), DegreeOrdering(), TNGraph::EndNI(), IncrementWeight(), TNGraph::IsEdge(), IsMotifM1(), IsMotifM2(), IsMotifM3(), IsMotifM4(), IsMotifM5(), IsMotifM6(), IsMotifM7(), TVec< TVal, TSizeTy >::Len(), M1, M2, M3, M4, M5, M6, M7, and TExcept::Throw().

Referenced by MotifAdjacency().

214  {
215  TIntV order;
216  DegreeOrdering(graph, order);
217  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
218  int src = NI.GetId();
219  int src_pos = order[src];
220 
221  // Get all neighbors who come later in the ordering
222  TIntV neighbors_higher;
223  for (int i = 0; i < NI.GetOutDeg(); i++) {
224  int nbr = NI.GetOutNId(i);
225  if (order[nbr] > src_pos) {
226  neighbors_higher.Add(nbr);
227  }
228  }
229  for (int i = 0; i < NI.GetInDeg(); i++) {
230  int nbr = NI.GetInNId(i);
231  if (!NI.IsOutNId(nbr) && order[nbr] > src_pos) {
232  neighbors_higher.Add(nbr);
233  }
234  }
235 
236  for (int ind1 = 0; ind1 < neighbors_higher.Len(); ind1++) {
237  for (int ind2 = ind1 + 1; ind2 < neighbors_higher.Len(); ind2++) {
238  int dst1 = neighbors_higher[ind1];
239  int dst2 = neighbors_higher[ind2];
240  // Check for triangle formation
241  if (graph->IsEdge(dst1, dst2) || graph->IsEdge(dst2, dst1)) {
242  bool motif_occurs = false;
243  switch (motif) {
244  case M1:
245  motif_occurs = IsMotifM1(graph, src, dst1, dst2);
246  break;
247  case M2:
248  motif_occurs = IsMotifM2(graph, src, dst1, dst2);
249  break;
250  case M3:
251  motif_occurs = IsMotifM3(graph, src, dst1, dst2);
252  break;
253  case M4:
254  motif_occurs = IsMotifM4(graph, src, dst1, dst2);
255  break;
256  case M5:
257  motif_occurs = IsMotifM5(graph, src, dst1, dst2);
258  break;
259  case M6:
260  motif_occurs = IsMotifM6(graph, src, dst1, dst2);
261  break;
262  case M7:
263  motif_occurs = IsMotifM7(graph, src, dst1, dst2);
264  break;
265  default:
266  TExcept::Throw("Unknown directed triangle motif");
267  }
268  // Increment weights of the triad (src, dst1, dst2) if it occurs.
269  if (motif_occurs) {
270  IncrementWeight(src, dst1, weights);
271  IncrementWeight(src, dst2, weights);
272  IncrementWeight(dst1, dst2, weights);
273  }
274  }
275  }
276  }
277  }
278 }
MotifCluster::IsMotifM2
static bool IsMotifM2(PNGraph graph, int u, int v, int w)
Definition: motifcluster.cpp:91
MotifCluster::IsMotifM7
static bool IsMotifM7(PNGraph graph, int u, int v, int w)
Definition: motifcluster.cpp:140
MotifCluster::IsMotifM4
static bool IsMotifM4(PNGraph graph, int u, int v, int w)
Definition: motifcluster.cpp:116
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
MotifCluster::IsMotifM1
static bool IsMotifM1(PNGraph graph, int u, int v, int w)
Definition: motifcluster.cpp:84
MotifCluster::IsMotifM3
static bool IsMotifM3(PNGraph graph, int u, int v, int w)
Definition: motifcluster.cpp:106
TExcept::Throw
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
IncrementWeight
static void IncrementWeight(int i, int j, WeightVH &weights)
Definition: motifcluster.cpp:29
MotifCluster::IsMotifM6
static bool IsMotifM6(PNGraph graph, int u, int v, int w)
Definition: motifcluster.cpp:131
MotifCluster::DegreeOrdering
static void DegreeOrdering(PNGraph graph, TIntV &order)
Definition: motifcluster.cpp:185
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
MotifCluster::IsMotifM5
static bool IsMotifM5(PNGraph graph, int u, int v, int w)
Definition: motifcluster.cpp:121
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

void MotifCluster::WedgeMotifAdjacency ( PNGraph  graph,
MotifType  motif,
WeightVH &  weights 
)
staticprivate

Definition at line 282 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegNI(), TNGraph::EndNI(), IncrementWeight(), IsMotifM10(), IsMotifM11(), IsMotifM12(), IsMotifM13(), IsMotifM8(), IsMotifM9(), TVec< TVal, TSizeTy >::Len(), M10, M11, M12, M13, M8, M9, and TExcept::Throw().

Referenced by MotifAdjacency().

283  {
284  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
285  int center = NI.GetId();
286 
287  // Get all neighbors
288  TIntV neighbors;
289  for (int i = 0; i < NI.GetOutDeg(); i++) {
290  int nbr = NI.GetOutNId(i);
291  neighbors.Add(nbr);
292  }
293  for (int i = 0; i < NI.GetInDeg(); i++) {
294  int nbr = NI.GetInNId(i);
295  if (!NI.IsOutNId(nbr)) {
296  neighbors.Add(nbr);
297  }
298  }
299 
300  for (int ind1 = 0; ind1 < neighbors.Len(); ind1++) {
301  for (int ind2 = ind1 + 1; ind2 < neighbors.Len(); ind2++) {
302  int dst1 = neighbors[ind1];
303  int dst2 = neighbors[ind2];
304  bool motif_occurs = false;
305  switch (motif) {
306  case M8:
307  motif_occurs = IsMotifM8(graph, center, dst1, dst2);
308  break;
309  case M9:
310  motif_occurs = IsMotifM9(graph, center, dst1, dst2);
311  break;
312  case M10:
313  motif_occurs = IsMotifM10(graph, center, dst1, dst2);
314  break;
315  case M11:
316  motif_occurs = IsMotifM11(graph, center, dst1, dst2);
317  break;
318  case M12:
319  motif_occurs = IsMotifM12(graph, center, dst1, dst2);
320  break;
321  case M13:
322  motif_occurs = IsMotifM13(graph, center, dst1, dst2);
323  break;
324  default:
325  TExcept::Throw("Unknown directed wedge motif");
326  }
327  // Increment weights of (center, dst1, dst2) if it occurs.
328  if (motif_occurs) {
329  IncrementWeight(center, dst1, weights);
330  IncrementWeight(center, dst2, weights);
331  IncrementWeight(dst1, dst2, weights);
332  }
333  }
334  }
335  }
336 }
MotifCluster::IsMotifM12
static bool IsMotifM12(PNGraph graph, int center, int v, int w)
Definition: motifcluster.cpp:171
MotifCluster::IsMotifM10
static bool IsMotifM10(PNGraph graph, int center, int v, int w)
Definition: motifcluster.cpp:160
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
MotifCluster::IsMotifM11
static bool IsMotifM11(PNGraph graph, int center, int v, int w)
Definition: motifcluster.cpp:165
MotifCluster::IsMotifM13
static bool IsMotifM13(PNGraph graph, int center, int v, int w)
Definition: motifcluster.cpp:177
TExcept::Throw
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
IncrementWeight
static void IncrementWeight(int i, int j, WeightVH &weights)
Definition: motifcluster.cpp:29
MotifCluster::IsMotifM9
static bool IsMotifM9(PNGraph graph, int center, int v, int w)
Definition: motifcluster.cpp:154
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
MotifCluster::IsMotifM8
static bool IsMotifM8(PNGraph graph, int center, int v, int w)
Definition: motifcluster.cpp:149
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

The documentation for this class was generated from the following files: