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
MAPPR Class Reference

#include <localmotifcluster.h>

Public Member Functions

 MAPPR ()
 
void computeAPPR (const ProcessedGraph &graph_p, const int SeedNodeId, float alpha, float eps)
 
void sweepAPPR (int option=-1)
 
THash< TInt, TFltgetAPPR ()
 
TIntV getCluster ()
 
void printAPPR ()
 
void printProfile ()
 

Private Member Functions

void computeProfile (const ProcessedGraph &graph_p)
 
void findGlobalMin ()
 
void findFirstlocalMin ()
 
bool isLocalMin (int idx, double thresh=1.2)
 

Private Attributes

THash< TInt, TFltappr_vec
 
int NumPushs
 
float appr_norm
 
TIntV NodeInOrder
 
TFltV MtfCondProfile
 
int SizeGlobalMin
 
int SizeFirstLocalMin
 
TIntV Cluster
 

Detailed Description

Definition at line 127 of file localmotifcluster.h.

Constructor & Destructor Documentation

MAPPR::MAPPR ( )

Definition at line 577 of file localmotifcluster.cpp.

577  {
578  NumPushs = 0;
579  appr_norm = 0;
580  SizeGlobalMin = 0;
581  SizeFirstLocalMin = -1;
582 }
int SizeFirstLocalMin
int SizeGlobalMin
float appr_norm

Member Function Documentation

void MAPPR::computeAPPR ( const ProcessedGraph graph_p,
const int  SeedNodeId,
float  alpha,
float  eps 
)

Definition at line 588 of file localmotifcluster.cpp.

588  {
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 }
THash< TInt, TFlt > appr_vec
void computeProfile(const ProcessedGraph &graph_p)
const WeightVH & getWeights() const
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
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
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:106
PUNGraph getTransformedGraph() const
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:214
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
float appr_norm
void MAPPR::computeProfile ( const ProcessedGraph graph_p)
private

Definition at line 637 of file localmotifcluster.cpp.

637  {
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 }
THash< TInt, TFlt > appr_vec
const WeightVH & getWeights() const
void findFirstlocalMin()
TIter BegI() const
Definition: hash.h:213
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TIter EndI() const
Definition: hash.h:218
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
TFltV MtfCondProfile
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:94
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
int AddKey(const TKey &Key)
Definition: shash.h:1254
void findGlobalMin()
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:106
PUNGraph getTransformedGraph() const
TIntV NodeInOrder
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
float getTotalVolume() const
void SortByDat(const bool &Asc=true)
Definition: hash.h:292
void MAPPR::findFirstlocalMin ( )
private

Definition at line 708 of file localmotifcluster.cpp.

708  {
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 }
int SizeFirstLocalMin
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TFltV MtfCondProfile
int SizeGlobalMin
void findGlobalMin()
bool isLocalMin(int idx, double thresh=1.2)
void MAPPR::findGlobalMin ( )
private

Definition at line 699 of file localmotifcluster.cpp.

699  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TFltV MtfCondProfile
int SizeGlobalMin
THash<TInt, TFlt> MAPPR::getAPPR ( )
inline

Definition at line 181 of file localmotifcluster.h.

181 { return appr_vec; };
THash< TInt, TFlt > appr_vec
TIntV MAPPR::getCluster ( )
inline

Definition at line 182 of file localmotifcluster.h.

182 { return Cluster; };
TIntV Cluster
bool MAPPR::isLocalMin ( int  idx,
double  thresh = 1.2 
)
private

Definition at line 681 of file localmotifcluster.cpp.

681  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TFltV MtfCondProfile
void MAPPR::printAPPR ( )

Definition at line 757 of file localmotifcluster.cpp.

757  {
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 }
THash< TInt, TFlt > appr_vec
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
Definition: hash.h:97
float appr_norm
void MAPPR::printProfile ( )

Definition at line 767 of file localmotifcluster.cpp.

767  {
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 }
int SizeFirstLocalMin
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TFltV MtfCondProfile
int SizeGlobalMin
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
TIntV NodeInOrder
void MAPPR::sweepAPPR ( int  option = -1)

Definition at line 730 of file localmotifcluster.cpp.

730  {
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 }
THash< TInt, TFlt > appr_vec
TIntV Cluster
int SizeFirstLocalMin
int SizeGlobalMin
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
void sweepAPPR(int option=-1)
TIntV NodeInOrder
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228

Member Data Documentation

float MAPPR::appr_norm
private

Definition at line 133 of file localmotifcluster.h.

THash<TInt, TFlt> MAPPR::appr_vec
private

Definition at line 129 of file localmotifcluster.h.

TIntV MAPPR::Cluster
private

Definition at line 145 of file localmotifcluster.h.

TFltV MAPPR::MtfCondProfile
private

Definition at line 137 of file localmotifcluster.h.

TIntV MAPPR::NodeInOrder
private

Definition at line 135 of file localmotifcluster.h.

int MAPPR::NumPushs
private

Definition at line 131 of file localmotifcluster.h.

int MAPPR::SizeFirstLocalMin
private

Definition at line 142 of file localmotifcluster.h.

int MAPPR::SizeGlobalMin
private

Definition at line 139 of file localmotifcluster.h.


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