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, TFlt >	getAPPR ()
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, TFlt >	appr_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.

             {
  NumPushs = 0;
  appr_norm = 0;
  SizeGlobalMin = 0;
  SizeFirstLocalMin = -1;
}

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.

                                                                                                   {
  appr_vec.Clr();
  THash<TInt, TFlt> residual;
  NumPushs = 0;
  appr_norm = 0;
  const WeightVH& Weights = graph_p.getWeights();
  if (Weights[SeedNodeId].GetDat(SeedNodeId) * eps >= 1) {
    appr_vec(SeedNodeId) = 0;
    return;
  }
  residual(SeedNodeId) = 1;
  TSnapQueue<int> NodesWExcesRes;
  NodesWExcesRes.Push(SeedNodeId);

  while (!NodesWExcesRes.Empty()) {
    NumPushs += 1;
    int NodeId = NodesWExcesRes.Top();
    NodesWExcesRes.Pop();

    float deg_w = Weights[NodeId].GetDat(NodeId);
    if (deg_w == 0) {
      appr_vec(NodeId) += residual(NodeId);
      appr_norm += residual(NodeId);
      residual(NodeId) = 0;
      continue;
    }
    float pushVal = residual(NodeId) - deg_w * eps / 2;
    appr_vec(NodeId) += pushVal * (1-alpha);
    appr_norm += pushVal * (1-alpha);
    residual(NodeId) = deg_w * eps / 2;

    pushVal *= alpha / deg_w;
    TUNGraph::TNodeI NI = graph_p.getTransformedGraph()->GetNI(NodeId);
    for (int i = 0; i < NI.GetOutDeg(); i ++) {
      int NbrId = NI.GetOutNId(i);
      float nbrValOld = residual(NbrId);
      float nbrValNew = nbrValOld + pushVal * Weights[NodeId].GetDat(NbrId);
      residual(NbrId) = nbrValNew;
      if (nbrValOld <= eps * Weights[NbrId].GetDat(NbrId)  &&  nbrValNew > eps * Weights[NbrId].GetDat(NbrId)) {
        NodesWExcesRes.Push(NbrId);
      }
    }
  }
  computeProfile(graph_p);
}

void MAPPR::computeProfile ( const ProcessedGraph &  graph_p )

private

Definition at line 637 of file localmotifcluster.cpp.

                                                        {
  THash<TInt, TFlt> Quotient;
  const WeightVH& Weights = graph_p.getWeights();
  for (THash<TInt, TFlt>::TIter it = appr_vec.BegI(); it < appr_vec.EndI(); it++) {
    int NodeId = it->Key;
    Quotient(NodeId) = it->Dat / Weights[NodeId].GetDat(NodeId);
  }
  Quotient.SortByDat(false);

  double vol = 0, cut = 0;
  TIntSet IsIn;           // the current set
  int VolSmall = 1;       // =1 if volume(IsIn) <= VolAll/2, and = -1 otherwise;
  float TotalVol = graph_p.getTotalVolume();

  for (THash<TInt, TFlt>::TIter it = Quotient.BegI(); it < Quotient.EndI(); it++) {
    int NodeId = it->Key;
    TUNGraph::TNodeI NI = graph_p.getTransformedGraph()->GetNI(NodeId);
    const THash<TInt, TFlt>& WeightsHere = Weights[NodeId];

    NodeInOrder.Add(NodeId);
    IsIn.AddKey(NodeId);
    vol += VolSmall * WeightsHere.GetDat(NodeId);
    if (VolSmall == 1 && vol >= TotalVol / 2) {
      vol = TotalVol - vol;
      VolSmall = -1;
    }
    cut += WeightsHere.GetDat(NodeId);
    for (long j = 0; j < NI.GetOutDeg(); j ++) {
      long NbrId = NI.GetOutNId(j);
      if (IsIn.IsKey(NbrId)) {
        cut -= 2 * WeightsHere.GetDat(NbrId);
      }
    }
    if (vol) {
      MtfCondProfile.Add(cut / vol);
    } else {
      MtfCondProfile.Add(1);
    }
  }
  findGlobalMin();
  findFirstlocalMin();
}

void MAPPR::findFirstlocalMin ( )

private

Definition at line 708 of file localmotifcluster.cpp.

                              {
  SizeFirstLocalMin = 2;
  while (SizeFirstLocalMin < MtfCondProfile.Len()) {
    if (isLocalMin(SizeFirstLocalMin-1)) {
      break;
    }
    SizeFirstLocalMin ++;
  }
  if (SizeFirstLocalMin >= MtfCondProfile.Len()) {   // If there is no local min, we take the global min
    if (SizeGlobalMin == 0) {
      findGlobalMin();
    }
    SizeFirstLocalMin = SizeGlobalMin;
  }
}

void MAPPR::findGlobalMin ( )

private

Definition at line 699 of file localmotifcluster.cpp.

                          {
  double minCondVal = 2;
  for (int i = 0; i < MtfCondProfile.Len(); i ++) {
    if (MtfCondProfile[i] < minCondVal) {
      SizeGlobalMin = i + 1;
      minCondVal = MtfCondProfile[i];
    }
  } 
}

THash<TInt, TFlt> MAPPR::getAPPR ( )

inline

Definition at line 181 of file localmotifcluster.h.

{ return appr_vec; };

TIntV MAPPR::getCluster ( )

inline

Definition at line 182 of file localmotifcluster.h.

{ return Cluster; };

bool MAPPR::isLocalMin ( int  idx, double  thresh = 1.2  )

private

Definition at line 681 of file localmotifcluster.cpp.

                                             {
    if (idx <= 0 || idx >= MtfCondProfile.Len() - 1) {
        return false;
    }
    if (MtfCondProfile[idx] >= MtfCondProfile[idx-1]) {
        return false;
    }
    int idxRight = idx;
    while (idxRight < MtfCondProfile.Len() - 1) {
        idxRight ++;
        if (MtfCondProfile[idxRight] > MtfCondProfile[idx] * thresh) {
            return true;
        } else if (MtfCondProfile[idxRight] <= MtfCondProfile[idx]) {
            return false;
        }
    }
    return false;
}

void MAPPR::printAPPR

(

)

Definition at line 757 of file localmotifcluster.cpp.

                      {
  for (THash<TInt, TFlt>::TIter it = appr_vec.BegI(); it < appr_vec.EndI(); it++) {
    int NodeId = it->Key;
    float VecVal = it->Dat;
    printf("%d : %.7f\n", NodeId, VecVal);
  }
  printf("Number of pushes: %d\n", NumPushs);
  printf("L1-norm of APPR vector: %.7f\n", appr_norm);
}

void MAPPR::printProfile

(

)

Definition at line 767 of file localmotifcluster.cpp.

                         {
  if (NodeInOrder.Len() == 0) {
    TExcept::Throw("No APPR vector has been computed! Please first do MAPPR::computeAPPR(...)!");
  }
  printf("Size\tNodeId\tConductance\n");
  for (int i = 0; i < NodeInOrder.Len(); i ++) {
    int NodeId = NodeInOrder[i];
    float Cond = MtfCondProfile[i];
    printf("%d\t%d\t%.7f\n", i+1, NodeId, Cond);
    if (i == SizeGlobalMin - 1) {
      printf("\tGlobal minimun!!!\n");
    }
    if (i == SizeFirstLocalMin - 1) {
      printf("\tFirst local minimun!!!\n");
    }
  }
}

void MAPPR::sweepAPPR

(

int

option = -1

)

Definition at line 730 of file localmotifcluster.cpp.

                                {
  if (appr_vec.Len() == 0) {
    TExcept::Throw("No APPR vector has been computed! Please first do MAPPR::computeAPPR(...)!");
  }

  if (option == 0) {  // use global min as output
    if (SizeGlobalMin == 0) {
      TExcept::Throw("A bug somewhere!");
    }
    sweepAPPR(SizeGlobalMin);
  } else if (option == -1) {
    if (SizeFirstLocalMin == -1) {
      TExcept::Throw("A bug somewhere!");
    }
    sweepAPPR(SizeFirstLocalMin);
  } else if (option > 0) {
    Cluster.Clr();
    for (int i = 0; i < option; i++) {
      Cluster.Add(NodeInOrder[i]);
    }
  } else {
    TExcept::Throw("Invalid input in option!");
  }
}

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:

• snap-adv/localmotifcluster.h
• snap-adv/localmotifcluster.cpp