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.h
Go to the documentation of this file.
1 #ifndef snap_motifcluster_h
2 #define snap_motifcluster_h
3 #include "Snap.h"
4 
5 const double kDefaultTol = 1e-12;
6 const int kMaxIter = 300;
7 
9 
10 enum MotifType {
11  M1, // u --> v, v --> w, w --> u
12  M2, // u <--> v, v --> w, w --> u
13  M3, // u <--> v, v <--> w, w --> u
14  M4, // u <--> v, v <--> w, w <--> u
15  M5, // u --> v, v --> w, u --> w
16  M6, // u <--> v, w --> u, w --> v
17  M7, // u <--> v, u --> w, v --> w
18  M8, // u --> v, u --> w
19  M9, // u --> v, w --> u
20  M10, // v --> u, w --> u
21  M11, // u <--> v, u --> w
22  M12, // u <--> v, w --> u
23  M13, // u <--> v, u <--> w
24  bifan, // u --> w, u --> x, v --> w, v --> x
25  semiclique, // u -- v, u -- w, u -- x, v -- w, v -- x
26  triangle, // undirected cliques
27  clique3, // |
28  clique4, // |
29  clique5, // |
30  clique6, // |
31  clique7, // |
32  clique8, // |
33  clique9, // |
34  edge, // (undirected) edges
35 };
36 
37 // Container for sweep cut data.
38 class TSweepCut {
39  public:
40  TIntV cluster; // Set of indices forming cluster
41  double cond; // conductance of the cluster
42  double eig; // Eigenvalue of Fiedler vector
43  TFltV sweep_profile; // Sweep profile: kth entry is conductance(Sk)
44  TCnCom component; // connected component that the cut runs on
45 };
46 
47 // Wrapper around ARPACK for computing the smallest algebraic eigenvalues of a
48 // matrix A. A is the matrix, nev is the number of eigenvectors to compute, tol
49 // is the stopping tolerance, and maxiter is the maximum number of iterations.
50 // This routine stores the eigenvalues in evals and the eigenvectors in evecs,
51 // sorted from smallest to largest eigenvalue.
52 void SymeigsSmallest(const TSparseColMatrix& A, int nev, TFltV& evals,
53  TFullColMatrix& evecs, double tol=kDefaultTol,
54  int maxiter=kMaxIter);
55 
56 class MotifCluster {
57  public:
58  // Given a graph and a motif type, uses the motif spectral clustering to find
59  // a motif-based cluster in the graph. The result of the method is stored in
60  // the sweepcut data structure. Optional parameters include the tolerance and
61  // maximum number of iterations for the underlying eigenvector routine.
62  static void GetMotifCluster(PNGraph graph, MotifType motif,
63  TSweepCut& sweepcut, double tol=kDefaultTol,
64  int maxiter=kMaxIter);
65  static void GetMotifCluster(PUNGraph graph, MotifType motif,
66  TSweepCut& sweepcut, double tol=kDefaultTol,
67  int maxiter=kMaxIter);
68 
69  // For a given graph, fill the weights vector with the weights in the motif
70  // adjacency matrix. Specifically, weights[i][j] is the number of times i and
71  // j co-occurr in an instance of the motif for any i < j (only stores the
72  // lower triangular part of the matrix).
73  static void MotifAdjacency(PNGraph graph, MotifType motif, WeightVH& weights);
74  static void MotifAdjacency(PUNGraph graph, MotifType motif, WeightVH& weights);
75 
76  // Given a weighted network, compute a cut of the graph using the Fiedler
77  // vector and a sweep cut. Results are stored in the sweepcut data structure.
78  // The variables tol and maxiter control the stopping tolerance and maximum
79  // number of iterations used by the eigensolver.
80  static void SpectralCut(const WeightVH& weights, TSweepCut& sweepcut,
81  double tol=kDefaultTol, int maxiter=kMaxIter);
82 
83  // Compute the normalized Fiedler vector for the normalized Laplacian of the
84  // graph corresponding to the nonnegative matrix W and store the result in
85  // fvec. The normalized Fiedler vector is the eigenvector corresponding to
86  // the second smallest eigenvalue of the normalized Laplacian, scaled by the
87  // inverse square root of the node degrees.
88  static double NFiedlerVector(const TSparseColMatrix& W, TFltV& fvec,
89  double tol=kDefaultTol, int maxiter=kMaxIter);
90 
91  // Given a string representation of a motif name, parse it to a MotifType.
92  static MotifType ParseMotifType(const TStr& motif);
93 
94  // Check if three nodes form an instance of a directed triangle motif.
95  static bool IsMotifM1(PNGraph graph, int u, int v, int w);
96  static bool IsMotifM2(PNGraph graph, int u, int v, int w);
97  static bool IsMotifM3(PNGraph graph, int u, int v, int w);
98  static bool IsMotifM4(PNGraph graph, int u, int v, int w);
99  static bool IsMotifM5(PNGraph graph, int u, int v, int w);
100  static bool IsMotifM6(PNGraph graph, int u, int v, int w);
101  static bool IsMotifM7(PNGraph graph, int u, int v, int w);
102  // Check if three nodes form a directed wedge motif with a specified center.
103  static bool IsMotifM8(PNGraph graph, int center, int v, int w);
104  static bool IsMotifM9(PNGraph graph, int center, int v, int w);
105  static bool IsMotifM10(PNGraph graph, int center, int v, int w);
106  static bool IsMotifM11(PNGraph graph, int center, int v, int w);
107  static bool IsMotifM12(PNGraph graph, int center, int v, int w);
108  static bool IsMotifM13(PNGraph graph, int center, int v, int w);
109 
110  // Check if u --> v is a unidirectional edge (u --> v but no v --> u).
111  static bool IsUnidirEdge(PNGraph graph, int u, int v);
112 
113  // Check if u and v form a bidirectional edge (u <--> v).
114  static bool IsBidirEdge(PNGraph graph, int u, int v);
115 
116  // Check if there is no edge between u and v
117  static bool IsNoEdge(PNGraph graph, int u, int v);
118 
119  // Fills order vector so that order[i] < order[j] implies that
120  // degree(i) <= degree(j),
121  // where degree is the number of unique incoming and outgoing neighbors
122  // (reciprocated edge neighbors are only counted once).
123  static void DegreeOrdering(PNGraph graph, TIntV& order);
124 
125  private:
126  // Handles MotifAdjacency() functionality for simple edges..
127  static void EdgeMotifAdjacency(PNGraph graph, WeightVH& weights);
128  static void EdgeMotifAdjacency(PUNGraph graph, WeightVH& weights);
129 
130 
131  // Handles MotifAdjacency() functionality for directed triangle motifs.
132  static void TriangleMotifAdjacency(PNGraph graph, MotifType motif,
133  WeightVH& weights);
134 
135  // Handles MotifAdjacency() functionality for directed wedges.
136  static void WedgeMotifAdjacency(PNGraph graph, MotifType motif,
137  WeightVH& weights);
138 
139  // Handles MotifAdjacency() functionality for the bifan motif.
140  static void BifanMotifAdjacency(PNGraph graph, WeightVH& weights);
141 
142  // Handles MotifAdjacency() functionality for the semi-clique.
143  static void SemicliqueMotifAdjacency(PUNGraph graph, WeightVH& weights);
144 
145  // Handles MotifAdjacency() functionality for undirected cliques.
146  static void CliqueMotifAdjacency(PUNGraph graph, int clique_size,
147  WeightVH& weights);
148 };
149 
150 // Helper Class for doing undirected clique adjacency matrix weighting. Uses
151 // the Chiba & Nishizeki algorithm with (k-1)-core preprocessing. See:
152 //
153 // Chiba, Norishige, and Takao Nishizeki. "Arboricity and subgraph listing
154 // algorithms." SIAM Journal on Computing 14.1 (1985): 210-223.
156  public:
158 
159  // Form motif adjacency matrix for cliques of size k
160  void Run(int k);
161 
162  // Get the weight vector
163  WeightVH& weights() { return weights_; }
164 
165  private:
166  // Get the order of nodes given by the subgraph induced by U
167  void SubgraphDegreeOrder(int k, const TIntV& U, TIntV& order);
168 
169  // Update the weights for all nodes participating in the clique
170  void UpdateWeights(const TIntV& clique);
171 
172  // Write out all of the cliques (nodes in U + the stack)
173  void FlushCliques(const TIntV& U);
174 
175  // Main recursive function
176  void CliqueEnum(int k, const TIntV& U);
177 
178  // Adjust neighbors with label k
179  void AdjustLabels(int kcurr, int klast, const TIntV& U);
180 
181  void Initialize(int k);
182 
186  int k_; // size of clique
188  WeightVH weights_; // motif adjacency weights
189 };
190 
191 #endif // snap_motifcluster_h
void AdjustLabels(int kcurr, int klast, const TIntV &U)
static bool IsMotifM12(PNGraph graph, int center, int v, int w)
void FlushCliques(const TIntV &U)
static MotifType ParseMotifType(const TStr &motif)
static bool IsMotifM10(PNGraph graph, int center, int v, int w)
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)
TIntV cluster
Definition: motifcluster.h:40
static bool IsMotifM11(PNGraph graph, int center, int v, int w)
const double kDefaultTol
Definition: motifcluster.h:5
double eig
Definition: motifcluster.h:42
static bool IsMotifM1(PNGraph graph, int u, int v, int w)
TCnCom component
Definition: motifcluster.h:44
void SubgraphDegreeOrder(int k, const TIntV &U, TIntV &order)
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsMotifM13(PNGraph graph, int center, int v, int w)
static bool IsMotifM3(PNGraph graph, int u, int v, int w)
Definition: cncom.h:88
void UpdateWeights(const TIntV &clique)
static void SpectralCut(const WeightVH &weights, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
static void MotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
TVec< THash< TInt, TInt > > WeightVH
Definition: motifcluster.h:8
static void WedgeMotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
void CliqueEnum(int k, const TIntV &U)
ChibaNishizekiWeighter(PUNGraph graph)
Definition: motifcluster.h:157
static void BifanMotifAdjacency(PNGraph graph, WeightVH &weights)
static bool IsMotifM9(PNGraph graph, int center, int v, int w)
static bool IsMotifM6(PNGraph graph, int u, int v, int w)
static void TriangleMotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
double cond
Definition: motifcluster.h:41
static bool IsUnidirEdge(PNGraph graph, int u, int v)
static void DegreeOrdering(PNGraph graph, TIntV &order)
Definition: dt.h:412
TFltV sweep_profile
Definition: motifcluster.h:43
MotifType
Definition: motifcluster.h:10
TVec< TVec< TIntV > > graph_
Definition: motifcluster.h:183
static double NFiedlerVector(const TSparseColMatrix &W, TFltV &fvec, double tol=kDefaultTol, int maxiter=kMaxIter)
void SymeigsSmallest(const TSparseColMatrix &A, int nev, TFltV &evals, TFullColMatrix &evecs, double tol=kDefaultTol, int maxiter=kMaxIter)
static bool IsMotifM5(PNGraph graph, int u, int v, int w)
const int kMaxIter
Definition: motifcluster.h:6
static bool IsMotifM8(PNGraph graph, int center, int v, int w)
static void SemicliqueMotifAdjacency(PUNGraph graph, WeightVH &weights)
static void CliqueMotifAdjacency(PUNGraph graph, int clique_size, WeightVH &weights)
static bool IsNoEdge(PNGraph graph, int u, int v)
static void GetMotifCluster(PNGraph graph, MotifType motif, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
static void EdgeMotifAdjacency(PNGraph graph, WeightVH &weights)