SNAP Library 3.0, User Reference  2016-07-20 17:56:49
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
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.

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 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
TIter BegI() const
Definition: hash.h:171
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIter EndI() const
Definition: hash.h:176
static void IncrementWeight(int i, int j, WeightVH &weights)
static bool IsUnidirEdge(PNGraph graph, int u, int v)
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:362
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:372
static bool IsNoEdge(PNGraph graph, int u, int v)
void MotifCluster::CliqueMotifAdjacency ( PUNGraph  graph,
int  clique_size,
WeightVH weights 
)
staticprivate

Definition at line 503 of file motifcluster.cpp.

504  {
505  ChibaNishizekiWeighter cnw(graph);
506  cnw.Run(clique_size);
507  weights = cnw.weights();
508 }
void MotifCluster::DegreeOrdering ( PNGraph  graph,
TIntV order 
)
static

Definition at line 185 of file motifcluster.cpp.

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 }
Definition: ds.h:345
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:487
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
TVec< TInt > TIntV
Definition: ds.h:1529
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
void MotifCluster::EdgeMotifAdjacency ( PNGraph  graph,
WeightVH weights 
)
staticprivate

Definition at line 443 of file motifcluster.cpp.

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 }
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:516
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:514
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:386
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
static void IncrementWeight(int i, int j, WeightVH &weights)
void MotifCluster::EdgeMotifAdjacency ( PUNGraph  graph,
WeightVH weights 
)
staticprivate

Definition at line 457 of file motifcluster.cpp.

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 }
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:117
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:241
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:239
static void IncrementWeight(int i, int j, WeightVH &weights)
void MotifCluster::GetMotifCluster ( PNGraph  graph,
MotifType  motif,
TSweepCut sweepcut,
double  tol = kDefaultTol,
int  maxiter = kMaxIter 
)
static

Definition at line 701 of file motifcluster.cpp.

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

Definition at line 709 of file motifcluster.cpp.

711  {
712  WeightVH weights;
713  MotifAdjacency(graph, motif, weights);
714  SpectralCut(weights, sweepcut, tol, maxiter);
715 }
static void SpectralCut(const WeightVH &weights, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
static void MotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
bool MotifCluster::IsBidirEdge ( PNGraph  graph,
int  u,
int  v 
)
static

Definition at line 80 of file motifcluster.cpp.

80  {
81  return graph->IsEdge(u, v) && graph->IsEdge(v, u);
82 }
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
bool MotifCluster::IsMotifM1 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 84 of file motifcluster.cpp.

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 }
static bool IsUnidirEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM10 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 160 of file motifcluster.cpp.

160  {
161  return IsNoEdge(graph, v, w) && IsUnidirEdge(graph, v, center) &&
162  IsUnidirEdge(graph, w, center);
163 }
static bool IsUnidirEdge(PNGraph graph, int u, int v)
static bool IsNoEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM11 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 165 of file motifcluster.cpp.

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 }
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsUnidirEdge(PNGraph graph, int u, int v)
static bool IsNoEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM12 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 171 of file motifcluster.cpp.

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 }
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsUnidirEdge(PNGraph graph, int u, int v)
static bool IsNoEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM13 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 177 of file motifcluster.cpp.

177  {
178  return IsNoEdge(graph, v, w) && IsBidirEdge(graph, center, v)
179  && IsBidirEdge(graph, center, w);
180 }
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsNoEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM2 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 91 of file motifcluster.cpp.

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 }
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsUnidirEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM3 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 106 of file motifcluster.cpp.

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 }
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsUnidirEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM4 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 116 of file motifcluster.cpp.

116  {
117  return IsBidirEdge(graph, u, v) && IsBidirEdge(graph, u, w) &&
118  IsBidirEdge(graph, v, w);
119 }
static bool IsBidirEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM5 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 121 of file motifcluster.cpp.

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 }
static bool IsUnidirEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM6 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 131 of file motifcluster.cpp.

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 }
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsUnidirEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM7 ( PNGraph  graph,
int  u,
int  v,
int  w 
)
static

Definition at line 140 of file motifcluster.cpp.

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 }
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsUnidirEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM8 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 149 of file motifcluster.cpp.

149  {
150  return IsNoEdge(graph, v, w) && IsUnidirEdge(graph, center, v) &&
151  IsUnidirEdge(graph, center, w);
152 }
static bool IsUnidirEdge(PNGraph graph, int u, int v)
static bool IsNoEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsMotifM9 ( PNGraph  graph,
int  center,
int  v,
int  w 
)
static

Definition at line 154 of file motifcluster.cpp.

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 }
static bool IsUnidirEdge(PNGraph graph, int u, int v)
static bool IsNoEdge(PNGraph graph, int u, int v)
bool MotifCluster::IsNoEdge ( PNGraph  graph,
int  u,
int  v 
)
static

Definition at line 72 of file motifcluster.cpp.

72  {
73  return !graph->IsEdge(u, v) && !graph->IsEdge(v, u);
74 }
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
bool MotifCluster::IsUnidirEdge ( PNGraph  graph,
int  u,
int  v 
)
static

Definition at line 76 of file motifcluster.cpp.

76  {
77  return graph->IsEdge(u, v) && !graph->IsEdge(v, u);
78 }
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
void MotifCluster::MotifAdjacency ( PNGraph  graph,
MotifType  motif,
WeightVH weights 
)
static

Definition at line 471 of file motifcluster.cpp.

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 }
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
TVec< THash< TInt, TInt > > WeightVH
Definition: motifcluster.h:8
static void WedgeMotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
static void BifanMotifAdjacency(PNGraph graph, WeightVH &weights)
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:487
static void TriangleMotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
static void EdgeMotifAdjacency(PNGraph graph, WeightVH &weights)
void MotifCluster::MotifAdjacency ( PUNGraph  graph,
MotifType  motif,
WeightVH weights 
)
static

Definition at line 510 of file motifcluster.cpp.

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 }
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:215
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
TVec< THash< TInt, TInt > > WeightVH
Definition: motifcluster.h:8
static void SemicliqueMotifAdjacency(PUNGraph graph, WeightVH &weights)
static void CliqueMotifAdjacency(PUNGraph graph, int clique_size, WeightVH &weights)
static void EdgeMotifAdjacency(PNGraph graph, WeightVH &weights)
double MotifCluster::NFiedlerVector ( const TSparseColMatrix W,
TFltV fvec,
double  tol = kDefaultTol,
int  maxiter = kMaxIter 
)
static

Definition at line 717 of file motifcluster.cpp.

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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:380
static double Sqrt(const double &x)
Definition: xmath.h:13
static void Normalize(TFltV &x)
Definition: linalg.cpp:328
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
int GetRows() const
Definition: linalg.h:45
int GetCols() const
Definition: linalg.h:47
void SymeigsSmallest(const TSparseColMatrix &A, int nev, TFltV &evals, TFullColMatrix &evecs, double tol, int maxiter)
TVec< TIntFltKdV > ColSpVV
Definition: linalg.h:60
void Multiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.h:24
TVec< TFltV > ColV
Definition: linalg.h:131
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
MotifType MotifCluster::ParseMotifType ( const TStr motif)
static

Definition at line 36 of file motifcluster.cpp.

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 }
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
TStr GetLc() const
Definition: dt.h:499
Definition: dt.h:412
void MotifCluster::SemicliqueMotifAdjacency ( PUNGraph  graph,
WeightVH weights 
)
staticprivate

Definition at line 405 of file motifcluster.cpp.

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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:90
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
static void IncrementWeight(int i, int j, WeightVH &weights)
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:211
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:107
bool IsEdge(const int &SrcNId, const int &DstNId) const
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition: graph.cpp:137
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:209
void MotifCluster::SpectralCut ( const WeightVH weights,
TSweepCut sweepcut,
double  tol = kDefaultTol,
int  maxiter = kMaxIter 
)
static

Definition at line 871 of file motifcluster.cpp.

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 }
TIter BegI() const
Definition: hash.h:171
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:380
TIntV cluster
Definition: motifcluster.h:40
TIter EndI() const
Definition: hash.h:176
double eig
Definition: motifcluster.h:42
TCnCom component
Definition: motifcluster.h:44
Definition: cncom.h:88
TIntV NIdV
Definition: cncom.h:90
static PUNGraph UnweightedGraphRepresentation(const WeightVH &weights)
bool IsNIdIn(const int &NId) const
Definition: cncom.h:110
double cond
Definition: motifcluster.h:41
TFltV sweep_profile
Definition: motifcluster.h:43
static double NFiedlerVector(const TSparseColMatrix &W, TFltV &fvec, double tol=kDefaultTol, int maxiter=kMaxIter)
static void MapIdsToFirstN(const TIntV &ids, THash< TInt, TInt > &id_map, TIntV &rev_id_map)
int Len() const
Definition: cncom.h:101
static void Sweep(const TSparseColMatrix &W, const TFltV &fvec, TFltV &conds, TIntV &order)
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376
void MotifCluster::TriangleMotifAdjacency ( PNGraph  graph,
MotifType  motif,
WeightVH weights 
)
staticprivate

Definition at line 213 of file motifcluster.cpp.

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 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
static bool IsMotifM2(PNGraph graph, int u, int v, int w)
static bool IsMotifM7(PNGraph graph, int u, int v, int w)
static bool IsMotifM4(PNGraph graph, int u, int v, int w)
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
static bool IsMotifM1(PNGraph graph, int u, int v, int w)
static bool IsMotifM3(PNGraph graph, int u, int v, int w)
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
static void IncrementWeight(int i, int j, WeightVH &weights)
static bool IsMotifM6(PNGraph graph, int u, int v, int w)
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
static void DegreeOrdering(PNGraph graph, TIntV &order)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
static bool IsMotifM5(PNGraph graph, int u, int v, int w)
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void MotifCluster::WedgeMotifAdjacency ( PNGraph  graph,
MotifType  motif,
WeightVH weights 
)
staticprivate

Definition at line 282 of file motifcluster.cpp.

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 }
static bool IsMotifM12(PNGraph graph, int center, int v, int w)
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
static bool IsMotifM10(PNGraph graph, int center, int v, int w)
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
static bool IsMotifM11(PNGraph graph, int center, int v, int w)
static bool IsMotifM13(PNGraph graph, int center, int v, int w)
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
static void IncrementWeight(int i, int j, WeightVH &weights)
static bool IsMotifM9(PNGraph graph, int center, int v, int w)
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
static bool IsMotifM8(PNGraph graph, int center, int v, int w)
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574

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