SNAP Library 4.0, User Reference  2017-07-27 13:18:06
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
localmotifcluster.cpp
Go to the documentation of this file.
1 #include "localmotifcluster.h"
2 #include "stdafx.h"
3 
4 
5 // void printVec(const TIntV& vec) {
6 // printf("[");
7 // for (int i = 0; i < vec.Len(); i ++) {
8 // int val = vec[i];
9 // printf("%d ", val);
10 // }
11 // printf("]\n");
12 // }
13 
14 
15 
16 /*
17 Section: Motif parsing and printing
18 */
19 // Given a string representation of a motif name, parse it to a MotifType.
20 MotifType ParseMotifType(const TStr& motif, const bool& IsDirected) {
21  TStr motif_lc = motif.GetLc();
22  if (IsDirected) {
23  if (motif_lc == "m1") { return M1; }
24  else if (motif_lc == "m2") { return M2; }
25  else if (motif_lc == "m3") { return M3; }
26  else if (motif_lc == "m4") { return M4; }
27  else if (motif_lc == "m5") { return M5; }
28  else if (motif_lc == "m6") { return M6; }
29  else if (motif_lc == "m7") { return M7; }
30  else if (motif_lc == "triad") { return triad; }
31  else if (motif_lc == "cycle") { return cycle; }
32  else if (motif_lc == "ffloop") { return FFLoop; }
33  else if (motif_lc == "unide") { return UniDE; }
34  else if (motif_lc == "bide") { return BiDE; }
35  else if (motif_lc == "de") { return DE; }
36  else if (motif_lc == "edge") { return DE_any; }
37  else {
38  TExcept::Throw("Unknown motif for directed graph!");
39  }
40  } else {
41  if (motif_lc == "uedge") { return UEdge; }
42  else if (motif_lc == "clique3") { return clique3; }
43  else if (motif_lc == "clique4") { return clique4; }
44  else if (motif_lc == "clique5") { return clique5; }
45  else if (motif_lc == "clique6") { return clique6; }
46  else if (motif_lc == "clique7") { return clique7; }
47  else if (motif_lc == "clique8") { return clique8; }
48  else if (motif_lc == "clique9") { return clique9; }
49  else { TExcept::Throw("Unknown motif for undirected graph!"); }
50  }
51  TExcept::Throw("Inappropriate input!");
52  return UEdge;
53 }
54 
55 // Print motif type, mainly for debugging use
56 void printMotifType(const MotifType& type) {
57  switch (type) {
58  case M1: printf("M1\n"); break;
59  case M2: printf("M2\n"); break;
60  case M3: printf("M3\n"); break;
61  case M4: printf("M4\n"); break;
62  case M5: printf("M5\n"); break;
63  case M6: printf("M6\n"); break;
64  case M7: printf("M7\n"); break;
65  case triad: printf("triad\n"); break;
66  case cycle: printf("cycle\n"); break;
67  case FFLoop: printf("FFLoop\n"); break;
68  case UniDE: printf("UniDE\n"); break;
69  case BiDE: printf("BiDE\n"); break;
70  case DE: printf("DE\n"); break;
71  case DE_any: printf("DE_any\n"); break;
72 
73  case UEdge: printf("UEdge\n"); break;
74  case clique3: printf("clique3\n"); break;
75  case clique4: printf("clique4\n"); break;
76  case clique5: printf("clique5\n"); break;
77  case clique6: printf("clique6\n"); break;
78  case clique7: printf("clique7\n"); break;
79  case clique8: printf("clique8\n"); break;
80  case clique9: printf("clique9\n"); break;
81 
82  default:
83  TExcept::Throw("Unknown motif type!");
84  }
85 }
86 
87 // Get the clique size from undirected motif type
88 int getCliqueSize(const MotifType& type) {
89  switch (type) {
90  case UEdge: return 2;
91  case clique3: return 3;
92  case clique4: return 4;
93  case clique5: return 5;
94  case clique6: return 6;
95  case clique7: return 7;
96  case clique8: return 8;
97  case clique9: return 9;
98  default: {
99  TExcept::Throw("Unknown motif for undirected graph!");
100  return -1;
101  }
102  }
103 }
104 
105 
106 
107 
108 
109 
110 /*
111 Section: Preprocessing unweighted graphs, including:
112 1. counting motif on each edge
113 2. obtain a transformed weighted graph.
114 */
115 
116 // Initializing for undirected graph input.
118  Graph_org = graph;
120 }
121 
122 // This function will return true if degree of nodeID1 is higher than nodeID2.
123 // If the degrees equal, it will return true if nodeID1 > nodeID2.
124 // Used in ChibaNishizeki's clique enumeration method
125 bool higherDeg(PUNGraph& G, TUNGraph::TNodeI& NI1, int nodeID2) {
126  TUNGraph::TNodeI NI2 = G->GetNI(nodeID2);
127  if (NI1.GetOutDeg() > NI2.GetOutDeg()) {
128  return true;
129  } else if (NI1.GetOutDeg() == NI2.GetOutDeg() && NI1.GetId() > nodeID2) {
130  return true;
131  } else {
132  return false;
133  }
134 }
135 bool higherDeg(PUNGraph& G, int nodeID1, int nodeID2) {
136  TUNGraph::TNodeI NI1 = G->GetNI(nodeID1);
137  return higherDeg(G, NI1, nodeID2);
138 }
139 
140 // This function counts the undirected graph motif (clique) instances on each edge.
141 // It uses recursive method for clique enumeration proposed by Chiba and Nishizeki (SIAM J. Comput. 1985).
142 // Input {int KSize} denotes the size of the clique we are to enumerate in the current graph {PUNGraph& G}
143 // Input {TIntV& PrevNodes} denotes a set of nodes that are directed connected to any node in the current graph G
144 // and {int level = PrevNodes.Len()} is the number of PreNodes. Therefore, any k-clique in G corresponds to
145 // a (k+level)-clique after all nodes in PrevNodes are added in the current graph G.
146 void ProcessedGraph::countClique(PUNGraph& G, int KSize, TIntV& PrevNodes, int level) {
147  // Each edge means a (level+2)-clique in the original graph!
148  if (level >= KSize - 1) {
149  throw "exception!!";
150  }
151  if (level >= 1) {
152  for (TUNGraph::TEdgeI EI = G->BegEI(); EI < G->EndEI(); EI ++ ) {
153  int SrcNId = EI.GetSrcNId();
154  int DstNId = EI.GetDstNId();
155  Counts[SrcNId](DstNId)[level-1] ++;
156  Counts[DstNId](SrcNId)[level-1] ++;
157  }
158  }
159  for (TUNGraph::TNodeI NI = G->BegNI(); NI < G->EndNI(); NI ++ ) {
160  int NodeId = NI.GetId();
161  int degHere = NI.GetOutDeg();
162  for (int i = 0; i < level; i ++) {
163  Counts[PrevNodes[i]](NodeId)[level-1] += degHere;
164  Counts[NodeId](PrevNodes[i])[level-1] += degHere;
165  }
166 
167  if (level == KSize - 2) {
168  continue;
169  }
170  // Go to the next level
171  PrevNodes[level] = NodeId;
172  TIntV neighborsID;
173  for (int e = 0; e < NI.GetOutDeg(); e++) {
174  int nbrID = NI.GetOutNId(e);
175  if (higherDeg(G, NodeId, nbrID)) {
176  neighborsID.Add(nbrID);
177  }
178  }
179  PUNGraph subGraph = TSnap::GetSubGraph(G, neighborsID);
180  int numEdges = subGraph->GetEdges();
181  for (int i = 0; i <= level; i ++) {
182  for (int j = i + 1; j <= level; j ++) {
183  Counts[PrevNodes[i]](PrevNodes[j])[level] += numEdges;
184  Counts[PrevNodes[j]](PrevNodes[i])[level] += numEdges;
185  }
186  }
187  countClique(subGraph, KSize, PrevNodes, level + 1);
188  }
189 }
190 
191 // Functions for undirected graph that
192 // 1) counts motifs on each pair of nodes
193 // 2) assign weights
194 // 3) obtain the transformed graph
197  Graph_trans = TSnap::ConvertGraph<PUNGraph>(Graph_org);
198  int KSize = getCliqueSize(mt);
199  if (KSize == 2) {
200  // Don't need to count, assign weights directly!
201  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
202  int NodeId = NI.GetId();
203  for (int e = 0; e < NI.GetOutDeg(); e++) {
204  Weights[NodeId](NI.GetOutNId(e)) = 1;
205  }
206  Weights[NodeId](NodeId) = NI.GetOutDeg();
207  }
208  TotalVol = 2 * Graph_org->GetEdges();
209  } else {
210  if (Counts.Len() == 0 || Counts.BegI()->Len() == 0 || Counts.BegI()->BegI()->Dat.Len() < KSize - 2) {
211  // If the KSize-clique has not been counted yet, then we count.
213  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
214  int NodeId = NI.GetId();
215  for (int e = 0; e < NI.GetOutDeg(); e++) {
216  Counts[NodeId](NI.GetOutNId(e)) = TIntV(KSize - 2);
217  }
218  }
219  TIntV PrevNodes(KSize - 2);
220  countClique(Graph_org, KSize, PrevNodes, 0);
221  }
222 
223  // Now we assign weights!
224  TotalVol = 0;
225  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
226  int NodeId = NI.GetId();
227  float deg_w = 0;
228  for (int e = 0; e < NI.GetOutDeg(); e++) {
229  int NbrId = NI.GetOutNId(e);
230  int MtfCntHere = Counts[NodeId](NbrId)[KSize-3];
231  if (MtfCntHere) {
232  Weights[NodeId](NbrId) = MtfCntHere;
233  deg_w += MtfCntHere;
234  } else {
235  Graph_trans->DelEdge(NodeId, NbrId);
236  }
237  }
238  Weights[NodeId](NodeId) = deg_w;
239  TotalVol += deg_w;
240  }
241  }
242 }
243 
244 
245 
246 // Initializing for directed graph input.
248  Graph_org = TSnap::ConvertGraph<PUNGraph>(graph);
249  countDirTriadMotif(graph);
250  assignWeights_dir(mt);
251 }
252 
253 // Check the edge information between nodeID and nbrID;
254 // It assume that nbrID is a neighbor of nodeID, either in-neighbor or out-neighbor;
255 // It will return
256 // 0: if nodeID <-> nbrID
257 // 1: if nodeID --> nbrID
258 // 2: if nodeID <-- nbrID
259 int checkEdge(PNGraph& G, long nodeID, long nbrID) {
260  if (G->IsEdge(nodeID, nbrID)) {
261  if (G->IsEdge(nbrID, nodeID)) {
262  return 0;
263  } else {
264  return 1;
265  }
266  } else {
267  return 2;
268  }
269 }
270 
271 // To check the motif types of the triad (nodeID, srcNId, dstNId).
272 // We have already known that (srcNId -> dstNId) is an edge in G
273 int checkTriadMotif(PNGraph& G, long nodeID, long srcNId, long dstNId) {
274  int motifType = 0;
275  if (G->IsEdge(dstNId, srcNId)) {
276  switch (checkEdge(G, nodeID, dstNId)) {
277  case 0: {
278  switch (checkEdge(G, nodeID, srcNId)) {
279  case 0: {
280  motifType = 4;
281  break;
282  }
283  case 1: {
284  motifType = 3;
285  break;
286  }
287  case 2: {
288  motifType = 3;
289  }
290  }
291  break;
292  }
293  case 1: {
294  switch (checkEdge(G, nodeID, srcNId)) {
295  case 0: {
296  motifType = 3;
297  break;
298  }
299  case 1: {
300  motifType = 6;
301  break;
302  }
303  case 2: {
304  motifType = 2;
305  }
306  }
307  break;
308  }
309  case 2: {
310  switch (checkEdge(G, nodeID, srcNId)) {
311  case 0: {
312  motifType = 3;
313  break;
314  }
315  case 1: {
316  motifType = 2;
317  break;
318  }
319  case 2: {
320  motifType = 7;
321  }
322  }
323  }
324  }
325  } else {
326  switch (checkEdge(G, nodeID, dstNId)) {
327  case 0: {
328  switch (checkEdge(G, nodeID, srcNId)) {
329  case 0: {
330  motifType = 3;
331  break;
332  }
333  case 1: {
334  motifType = 2;
335  break;
336  }
337  case 2: {
338  motifType = 6;
339  }
340  }
341  break;
342  }
343  case 1: {
344  switch (checkEdge(G, nodeID, srcNId)) {
345  case 0: {
346  motifType = 7;
347  break;
348  }
349  case 1: {
350  motifType = 5;
351  break;
352  }
353  case 2: {
354  motifType = 5;
355  }
356  }
357  break;
358  }
359  case 2: {
360  switch (checkEdge(G, nodeID, srcNId)) {
361  case 0: {
362  motifType = 2;
363  break;
364  }
365  case 1: {
366  motifType = 1;
367  break;
368  }
369  case 2: {
370  motifType = 5;
371  }
372  }
373  }
374  }
375  }
376  return motifType;
377 }
378 
379 // This function will return true if the out-degree of nodeID1 is higher than nodeID2.
380 // If the degrees equal, it will return true if nodeID1 > nodeID2.
381 // Used in ChibaNishizeki's clique enumeration method
382 bool higherDeg(PNGraph& G, TNGraph::TNodeI& NI1, int nodeID2) {
383  TNGraph::TNodeI NI2 = G->GetNI(nodeID2);
384  if (NI1.GetOutDeg() > NI2.GetOutDeg()) {
385  return true;
386  } else if (NI1.GetOutDeg() == NI2.GetOutDeg() && NI1.GetId() > nodeID2) {
387  return true;
388  } else {
389  return false;
390  }
391 }
392 bool higherDeg(PNGraph& G, int nodeID1, int nodeID2) {
393  TNGraph::TNodeI NI1 = G->GetNI(nodeID1);
394  return higherDeg(G, NI1, nodeID2);
395 }
396 
397 // To count the directed triangle motifs
399  int numBasicDirMtf = 9;
401  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
402  int NodeId = NI.GetId();
403  for (int e = 0; e < NI.GetOutDeg(); e++) {
404  Counts[NodeId](NI.GetOutNId(e)) = TIntV(numBasicDirMtf);
405  }
406  }
407  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI ++ ) {
408  long nodeID = NI.GetId();
409  TIntV neighborsID;
410  for (long e = 0; e < NI.GetOutDeg(); e++) {
411  long nbrID = NI.GetOutNId(e);
412  if (higherDeg(graph, nodeID, nbrID)) {
413  neighborsID.Add(nbrID);
414  Counts[nodeID](nbrID)[0] ++;
415  Counts[nbrID](nodeID)[0] ++;
416  }
417  }
418  for (long e = 0; e < NI.GetInDeg(); e++) {
419  long nbrID = NI.GetInNId(e);
420  if (higherDeg(graph, nodeID, nbrID)) {
421  if (graph->IsEdge(nodeID, nbrID)) {
422  Counts[nodeID](nbrID)[0] --;
423  Counts[nbrID](nodeID)[0] --;
424  Counts[nodeID](nbrID)[1] ++;
425  Counts[nbrID](nodeID)[1] ++;
426  } else {
427  neighborsID.Add(nbrID);
428  Counts[nodeID](nbrID)[0] ++;
429  Counts[nbrID](nodeID)[0] ++;
430  }
431  }
432  }
433  PNGraph subGraph = TSnap::GetSubGraph(graph, neighborsID);
434  for (TNGraph::TEdgeI EI = subGraph->BegEI(); EI < subGraph->EndEI(); EI ++ ) {
435  long srcNId = EI.GetSrcNId();
436  long dstNId = EI.GetDstNId();
437  int MotifNumber = 0;
438  if (srcNId > dstNId || !subGraph->IsEdge(dstNId, srcNId)) {
439  MotifNumber = checkTriadMotif(graph, nodeID, srcNId, dstNId);
440  MotifNumber ++;
441  Counts[nodeID](srcNId)[MotifNumber] ++;
442  Counts[srcNId](nodeID)[MotifNumber] ++;
443  Counts[nodeID](dstNId)[MotifNumber] ++;
444  Counts[dstNId](nodeID)[MotifNumber] ++;
445  Counts[srcNId](dstNId)[MotifNumber] ++;
446  Counts[dstNId](srcNId)[MotifNumber] ++;
447  }
448  }
449  }
450  return;
451 }
452 
453 // Functions for directed graph that
454 // 1) counts motifs on each pair of nodes
455 // 2) assign weights
456 // 3) obtain the transformed graph
458  TIntV MtfInclude;
459  switch (mt) {
460  case UniDE : {MtfInclude.Add(0); break;}
461  case BiDE : MtfInclude.Add(1); break;
462  case DE : MtfInclude.Add(0); MtfInclude.Add(1); MtfInclude.Add(1); break;
463  case DE_any : MtfInclude.Add(0); MtfInclude.Add(1); break;
464 
465  case M1 : MtfInclude.Add(2); break;
466  case M2 : MtfInclude.Add(3); break;
467  case M3 : MtfInclude.Add(4); break;
468  case M4 : MtfInclude.Add(5); break;
469  case M5 : MtfInclude.Add(6); break;
470  case M6 : MtfInclude.Add(7); break;
471  case M7 : MtfInclude.Add(8); break;
472  case triad : {
473  MtfInclude.Add(2);
474  MtfInclude.Add(3);
475  MtfInclude.Add(4);
476  MtfInclude.Add(5);
477  MtfInclude.Add(6);
478  MtfInclude.Add(7);
479  MtfInclude.Add(8);
480  break;
481  }
482  case cycle : {
483  MtfInclude.Add(2);
484  MtfInclude.Add(3);
485  MtfInclude.Add(4);
486  MtfInclude.Add(5);
487  MtfInclude.Add(5);
488  break;
489  }
490  case FFLoop : {
491  MtfInclude.Add(6);
492  MtfInclude.Add(7);
493  MtfInclude.Add(7);
494  MtfInclude.Add(8);
495  MtfInclude.Add(8);
496  break;
497  default:
498  TExcept::Throw("Unknown motif type!");
499  }
500  }
501 
502  Graph_trans = TSnap::ConvertGraph<PUNGraph>(Graph_org);
504 
505  TotalVol = 0;
506  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
507  int NodeId = NI.GetId();
508  float deg_w = 0;
509  for (int e = 0; e < NI.GetOutDeg(); e++) {
510  int NbrId = NI.GetOutNId(e);
511  TIntV& CountHere = Counts[NodeId](NbrId);
512  int WeightHere = 0;
513  for (int i = 0; i < MtfInclude.Len(); i ++) {
514  WeightHere += CountHere[MtfInclude[i]];
515  }
516  if (WeightHere) {
517  Weights[NodeId](NbrId) = WeightHere;
518  deg_w += WeightHere;
519  } else {
520  Graph_trans->DelEdge(NodeId, NbrId);
521  }
522  }
523  Weights[NodeId](NodeId) = deg_w;
524  TotalVol += deg_w;
525  }
526 
527  return;
528 }
529 
530 
532  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
533  int NodeId = NI.GetId();
534  for (int e = 0; e < NI.GetOutDeg(); e++) {
535  int NbrId = NI.GetOutNId(e);
536  TIntV& CountThisEdge = Counts[NodeId](NbrId);
537  printf("(%d, %d): ", NodeId, NbrId);
538  for (int i = 0; i < CountThisEdge.Len(); i ++) {
539  int output = CountThisEdge[i];
540  printf("%d ", output);
541  }
542  printf("\n");
543  }
544  }
545 }
546 
548  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
549  int NodeId = NI.GetId();
550  for (int e = 0; e < NI.GetOutDeg(); e++) {
551  int NbrId = NI.GetOutNId(e);
552  printf("(%d, %d): ", NodeId, NbrId);
553  if (Weights[NodeId].IsKey(NbrId)) {
554  float weight = Weights[NodeId](NbrId);
555  printf("%.2f ", weight);
556  } else {
557  printf("Not a key in Weights");
558  }
559  printf("\n");
560  }
561  float d_w = Weights[NodeId](NodeId);
562  printf("\td_w(%d) = %.2f.\n", NodeId, d_w);
563  }
564  printf("Total volume = %.2f. \n", TotalVol);
565  Graph_trans->Dump();
566 }
567 
568 
569 
570 
571 
572 /*
573 Section: MAPPR main part, including:
574 1. compute the APPR vector on the weighted transformed graph
575 2. obtain the cluster by sweeping the NCP profile
576 */
578  NumPushs = 0;
579  appr_norm = 0;
580  SizeGlobalMin = 0;
581  SizeFirstLocalMin = -1;
582 }
583 
584 // Function to compute the APPR vector on the weighted transformed graph {ProcessedGraph graph_p}
585 // with seed {int SeedNodeId} alpha = {float alpha}, and epsilon = {float eps}.
586 // It will also compute the NCP as well as with {SizeGlobalMin} and {SizeFirstLocalMin}, using {computeProfile(*)}.
587 // Results are stored in {this->appr_vec}, {this->NodeInOrder, MtfCondProfile}, and {this->SizeGlobalMin, SizeFirstLocalMin}.
588 void MAPPR::computeAPPR(const ProcessedGraph& graph_p, const int SeedNodeId, float alpha, float eps) {
589  appr_vec.Clr();
590  THash<TInt, TFlt> residual;
591  NumPushs = 0;
592  appr_norm = 0;
593  const WeightVH& Weights = graph_p.getWeights();
594  if (Weights[SeedNodeId].GetDat(SeedNodeId) * eps >= 1) {
595  appr_vec(SeedNodeId) = 0;
596  return;
597  }
598  residual(SeedNodeId) = 1;
599  TSnapQueue<int> NodesWExcesRes;
600  NodesWExcesRes.Push(SeedNodeId);
601 
602  while (!NodesWExcesRes.Empty()) {
603  NumPushs += 1;
604  int NodeId = NodesWExcesRes.Top();
605  NodesWExcesRes.Pop();
606 
607  float deg_w = Weights[NodeId].GetDat(NodeId);
608  if (deg_w == 0) {
609  appr_vec(NodeId) += residual(NodeId);
610  appr_norm += residual(NodeId);
611  residual(NodeId) = 0;
612  continue;
613  }
614  float pushVal = residual(NodeId) - deg_w * eps / 2;
615  appr_vec(NodeId) += pushVal * (1-alpha);
616  appr_norm += pushVal * (1-alpha);
617  residual(NodeId) = deg_w * eps / 2;
618 
619  pushVal *= alpha / deg_w;
620  TUNGraph::TNodeI NI = graph_p.getTransformedGraph()->GetNI(NodeId);
621  for (int i = 0; i < NI.GetOutDeg(); i ++) {
622  int NbrId = NI.GetOutNId(i);
623  float nbrValOld = residual(NbrId);
624  float nbrValNew = nbrValOld + pushVal * Weights[NodeId].GetDat(NbrId);
625  residual(NbrId) = nbrValNew;
626  if (nbrValOld <= eps * Weights[NbrId].GetDat(NbrId) && nbrValNew > eps * Weights[NbrId].GetDat(NbrId)) {
627  NodesWExcesRes.Push(NbrId);
628  }
629  }
630  }
631  computeProfile(graph_p);
632 }
633 
634 // To compute the NCP of the graph with precomputed APPR vector
635 // Results are stored in {this->NodeInOrder and MtfCondProfile}.
636 // It will also compute the global min and first local min of the NCP.
637 void MAPPR::computeProfile(const ProcessedGraph& graph_p) {
638  THash<TInt, TFlt> Quotient;
639  const WeightVH& Weights = graph_p.getWeights();
640  for (THash<TInt, TFlt>::TIter it = appr_vec.BegI(); it < appr_vec.EndI(); it++) {
641  int NodeId = it->Key;
642  Quotient(NodeId) = it->Dat / Weights[NodeId].GetDat(NodeId);
643  }
644  Quotient.SortByDat(false);
645 
646  double vol = 0, cut = 0;
647  TIntSet IsIn; // the current set
648  int VolSmall = 1; // =1 if volume(IsIn) <= VolAll/2, and = -1 otherwise;
649  float TotalVol = graph_p.getTotalVolume();
650 
651  for (THash<TInt, TFlt>::TIter it = Quotient.BegI(); it < Quotient.EndI(); it++) {
652  int NodeId = it->Key;
653  TUNGraph::TNodeI NI = graph_p.getTransformedGraph()->GetNI(NodeId);
654  const THash<TInt, TFlt>& WeightsHere = Weights[NodeId];
655 
656  NodeInOrder.Add(NodeId);
657  IsIn.AddKey(NodeId);
658  vol += VolSmall * WeightsHere.GetDat(NodeId);
659  if (VolSmall == 1 && vol >= TotalVol / 2) {
660  vol = TotalVol - vol;
661  VolSmall = -1;
662  }
663  cut += WeightsHere.GetDat(NodeId);
664  for (long j = 0; j < NI.GetOutDeg(); j ++) {
665  long NbrId = NI.GetOutNId(j);
666  if (IsIn.IsKey(NbrId)) {
667  cut -= 2 * WeightsHere.GetDat(NbrId);
668  }
669  }
670  if (vol) {
671  MtfCondProfile.Add(cut / vol);
672  } else {
673  MtfCondProfile.Add(1);
674  }
675  }
676  findGlobalMin();
678 }
679 
680 // Functions to find the global min and first local min of NCP.
681 bool MAPPR::isLocalMin(int idx, double thresh) {
682  if (idx <= 0 || idx >= MtfCondProfile.Len() - 1) {
683  return false;
684  }
685  if (MtfCondProfile[idx] >= MtfCondProfile[idx-1]) {
686  return false;
687  }
688  int idxRight = idx;
689  while (idxRight < MtfCondProfile.Len() - 1) {
690  idxRight ++;
691  if (MtfCondProfile[idxRight] > MtfCondProfile[idx] * thresh) {
692  return true;
693  } else if (MtfCondProfile[idxRight] <= MtfCondProfile[idx]) {
694  return false;
695  }
696  }
697  return false;
698 }
700  double minCondVal = 2;
701  for (int i = 0; i < MtfCondProfile.Len(); i ++) {
702  if (MtfCondProfile[i] < minCondVal) {
703  SizeGlobalMin = i + 1;
704  minCondVal = MtfCondProfile[i];
705  }
706  }
707 }
709  SizeFirstLocalMin = 2;
710  while (SizeFirstLocalMin < MtfCondProfile.Len()) {
711  if (isLocalMin(SizeFirstLocalMin-1)) {
712  break;
713  }
715  }
716  if (SizeFirstLocalMin >= MtfCondProfile.Len()) { // If there is no local min, we take the global min
717  if (SizeGlobalMin == 0) {
718  findGlobalMin();
719  }
721  }
722 }
723 
724 // Function to find the desired cluster based on the NCP.
725 // Option > 0 will give the cluster of size option;
726 // Option = 0 will give the cluster of global minimum conductance;
727 // Option = -1 will give the cluster of first local minimum in the NCP.
728 // Result is stored in {TIntV Cluster}.
729 // Note that this function can only be run after finishing {computeAPPR(...)}
730 void MAPPR::sweepAPPR(int option) {
731  if (appr_vec.Len() == 0) {
732  TExcept::Throw("No APPR vector has been computed! Please first do MAPPR::computeAPPR(...)!");
733  }
734 
735  if (option == 0) { // use global min as output
736  if (SizeGlobalMin == 0) {
737  TExcept::Throw("A bug somewhere!");
738  }
740  } else if (option == -1) {
741  if (SizeFirstLocalMin == -1) {
742  TExcept::Throw("A bug somewhere!");
743  }
745  } else if (option > 0) {
746  Cluster.Clr();
747  for (int i = 0; i < option; i++) {
748  Cluster.Add(NodeInOrder[i]);
749  }
750  } else {
751  TExcept::Throw("Invalid input in option!");
752  }
753 }
754 
755 
756 
758  for (THash<TInt, TFlt>::TIter it = appr_vec.BegI(); it < appr_vec.EndI(); it++) {
759  int NodeId = it->Key;
760  float VecVal = it->Dat;
761  printf("%d : %.7f\n", NodeId, VecVal);
762  }
763  printf("Number of pushes: %d\n", NumPushs);
764  printf("L1-norm of APPR vector: %.7f\n", appr_norm);
765 }
766 
768  if (NodeInOrder.Len() == 0) {
769  TExcept::Throw("No APPR vector has been computed! Please first do MAPPR::computeAPPR(...)!");
770  }
771  printf("Size\tNodeId\tConductance\n");
772  for (int i = 0; i < NodeInOrder.Len(); i ++) {
773  int NodeId = NodeInOrder[i];
774  float Cond = MtfCondProfile[i];
775  printf("%d\t%d\t%.7f\n", i+1, NodeId, Cond);
776  if (i == SizeGlobalMin - 1) {
777  printf("\tGlobal minimun!!!\n");
778  }
779  if (i == SizeFirstLocalMin - 1) {
780  printf("\tFirst local minimun!!!\n");
781  }
782  }
783 }
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
THash< TInt, TFlt > appr_vec
void computeAPPR(const ProcessedGraph &graph_p, const int SeedNodeId, float alpha, float eps)
void countClique(PUNGraph &G, int KSize, TIntV &PrevNodes, int level)
void assignWeights_undir(MotifType mt)
TDat Dat
Definition: hash.h:13
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
void computeProfile(const ProcessedGraph &graph_p)
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:276
const WeightVH & getWeights() const
TIntV Cluster
void findFirstlocalMin()
TVec< THash< TInt, TIntV > > CountVH
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
int checkTriadMotif(PNGraph &G, long nodeID, long srcNId, long dstNId)
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:588
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:243
int SizeFirstLocalMin
MotifType ParseMotifType(const TStr &motif, const bool &IsDirected)
TIter BegI() const
Definition: hash.h:213
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:586
void printAPPR()
bool higherDeg(PUNGraph &G, TUNGraph::TNodeI &NI1, int nodeID2)
void assignWeights_dir(MotifType mt)
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:207
MotifType
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TIter EndI() const
Definition: hash.h:218
void countDirTriadMotif(PNGraph graph)
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
TFltV MtfCondProfile
int SizeGlobalMin
void Pop()
Removes the first element from the queue.
Definition: gbase.h:198
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:186
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:94
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:426
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
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
PUNGraph GetSubGraph(const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumb...
Definition: subgraph.cpp:7
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:274
int AddKey(const TKey &Key)
Definition: shash.h:1254
TStr GetLc() const
Definition: dt.h:499
int checkEdge(PNGraph &G, long nodeID, long nbrID)
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
TVec< THash< TInt, TFlt > > WeightVH
void sweepAPPR(int option=-1)
void printProfile()
void findGlobalMin()
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
int GetId() const
Returns ID of the current node.
Definition: graph.h:396
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:106
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
Definition: dt.h:412
PUNGraph getTransformedGraph() const
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:201
TIntV NodeInOrder
int getCliqueSize(const MotifType &type)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TVec< TInt > TIntV
Definition: ds.h:1594
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:196
int GetId() const
Returns ID of the current node.
Definition: graph.h:88
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
bool isLocalMin(int idx, double thresh=1.2)
int Len() const
Definition: hash.h:228
float getTotalVolume() const
float appr_norm
void printMotifType(const MotifType &type)
void SortByDat(const bool &Asc=true)
Definition: hash.h:292