SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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:548
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:280
const WeightVH & getWeights() const
TIntV Cluster
void findFirstlocalMin()
TVec< THash< TInt, TIntV > > CountVH
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:596
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:594
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:211
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:199
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:430
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:278
int AddKey(const TKey &Key)
Definition: shash.h:1254
TStr GetLc() const
Definition: dt.h:502
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:550
int GetId() const
Returns ID of the current node.
Definition: graph.h:400
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:406
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:214
TIntV NodeInOrder
int getCliqueSize(const MotifType &type)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
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:209
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