TAGMUtil Class Reference

Affiliation Graph Model (AGM) graph generator. More...

#include <agm.h>

Static Public Member Functions
static void	GenPLSeq (TIntV &SzSeq, const int &SeqLen, const double &Alpha, TRnd &Rnd, const int &Min, const int &Max)
	AGMUtil:: Utilities for AGM. More...
static void	ConnectCmtyVV (TVec< TIntV > &CmtyVV, const TIntPrV &CIDSzPrV, const TIntPrV &NIDMemPrV, TRnd &Rnd)
	Generate bipartite community affiliation from given power law coefficients for membership distribution and community size distribution. More...
static void	GenCmtyVVFromPL (TVec< TIntV > &CmtyVV, const PUNGraph &Graph, const int &Nodes, const int &Coms, const double &ComSzAlpha, const double &MemAlpha, const int &MinSz, const int &MaxSz, const int &MinK, const int &MaxK, TRnd &Rnd)
	Generate bipartite community affiliation from given power law coefficients for membership distribution and community size distribution. More...
static void	GenCmtyVVFromPL (TVec< TIntV > &CmtyVV, const TIntV &NIDV, const int &Nodes, const int &Coms, const double &ComSzAlpha, const double &MemAlpha, const int &MinSz, const int &MaxSz, const int &MinK, const int &MaxK, TRnd &Rnd)
	Generate bipartite community affiliation from given power law coefficients for membership distribution and community size distribution. More...
static void	GenCmtyVVFromPL (TVec< TIntV > &CmtyVV, const int &Nodes, const int &Coms, const double &ComSzAlpha, const double &MemAlpha, const int &MinSz, const int &MaxSz, const int &MinK, const int &MaxK, TRnd &Rnd)
	Generate bipartite community affiliation from given power law coefficients for membership distribution and community size distribution. More...
static void	GetNodeMembership (THash< TInt, TIntSet > &NIDComVH, const TVec< TIntV > &CmtyVV)
	get hash table of <Node ID, community IDs which node belongs to> More...
static void	GetNodeMembership (THash< TInt, TIntSet > &NIDComVH, const TVec< TIntV > &CmtyVV, const TIntV &NIDV)
	get hash table of <Node ID, community IDs which node belongs to>. Some nodes in NIDV might belong to no community More...
static void	GetNodeMembership (TIntH &NIDComVH, const THash< TInt, TIntV > &CmtyVH)
	get hash table of <Node ID, membership size> More...
static void	GetNodeMembership (THash< TInt, TIntSet > &NIDComVH, const TVec< TIntSet > &CmtyVV)
static void	GetNodeMembership (THash< TInt, TIntSet > &NIDComVH, const THash< TInt, TIntV > &CmtyVH)
static void	GetNodeMembership (THash< TInt, TIntV > &NIDComVH, const THash< TInt, TIntV > &CmtyVH)
static void	GetNodeMembership (THash< TInt, TIntV > &NIDComVH, const TVec< TIntV > &CmtyVV)
static void	LoadCmtyVV (const TStr &InFNm, TVec< TIntV > &CmtyVV)
	load bipartite community affiliation graph from text file (each row contains the member node IDs for each community) More...
static void	LoadCmtyVV (const TStr &InFNm, TVec< TIntV > &CmtyVV, TStrHash< TInt > &StrToNIdH, const int BeginCol, const int MinSz=3, const TSsFmt Sep=ssfTabSep)
	load bipartite community affiliation graph from text file (each row contains the member node IDs for each community) More...
static void	DumpCmtyVV (const TStr &OutFNm, const TVec< TIntV > &CmtyVV)
	dump bipartite community affiliation into a text file More...
static void	DumpCmtyVV (const TStr OutFNm, TVec< TIntV > &CmtyVV, TIntStrH &NIDNmH)
	dump bipartite community affiliation into a text file with node names More...
static int	TotalMemberships (const TVec< TIntV > &CmtyVV)
	total number of memberships (== sum of the sizes of communities) More...
static void	RewireCmtyVV (const TVec< TIntV > &CmtyVVIn, TVec< TIntV > &CmtyVVOut, TRnd &Rnd)
	rewire bipartite community affiliation graphs More...
static void	RewireCmtyNID (THash< TInt, TIntV > &CmtyVH, TRnd &Rnd)
	rewire bipartite community affiliation graphs More...
static int	Intersection (const TIntV &C1, const TIntV &C2)
static void	GetIntersection (const THashSet< TInt > &A, const THashSet< TInt > &B, THashSet< TInt > &C)
static int	Intersection (const THashSet< TInt > &A, const THashSet< TInt > &B)
static double	GetConductance (const PUNGraph &Graph, const TIntSet &CmtyS, const int Edges)
static void	GetNbhCom (const PUNGraph &Graph, const int NID, TIntSet &NBCmtyS)
static void	SaveGephi (const TStr &OutFNm, const PUNGraph &G, const TVec< TIntV > &CmtyVVAtr, const double MaxSz, const double MinSz)
static void	SaveGephi (const TStr &OutFNm, const PUNGraph &G, const TVec< TIntV > &CmtyVVAtr, const double MaxSz, const double MinSz, const THash< TInt, TStr > &NIDNameH)
static void	SaveGephi (const TStr &OutFNm, const PUNGraph &G, const TVec< TIntV > &CmtyVVAtr, const double MaxSz, const double MinSz, const THash< TInt, TStr > &NIDNameH, const THash< TInt, TIntTr > &NIDColorH)
	save graph into a gexf file which Gephi can read More...
static void	SaveBipartiteGephi (const TStr &OutFNm, const TIntV &NIDV, const TVec< TIntV > &CmtyVV, const double MaxSz, const double MinSz, const TIntStrH &NIDNameH, const THash< TInt, TIntTr > &NIDColorH, const THash< TInt, TIntTr > &CIDColorH)
	save bipartite community affiliation into gexf file More...
static int	FindComsByAGM (const PUNGraph &Graph, const int InitComs, const int MaxIter, const int RndSeed, const double RegGap, const double PNoCom=0.0, const TStr PltFPrx=TStr())
	estimate number of communities using AGM More...
template<class PGraph >
static PGraph	LoadEdgeListStr (const TStr &InFNm, TIntStrH &NIDNameH, const int &SrcColId=0, const int &DstColId=1, const TSsFmt SsFmt=ssfTabSep)
template<class PGraph >
static PGraph	LoadEdgeListStr (const TStr &InFNm, TStrHash< TInt > &NodeNameH, const int &SrcColId=0, const int &DstColId=1, const TSsFmt SsFmt=ssfTabSep)
template<class PGraph >
static void	GVizComGraph (const PGraph &Graph, const TVec< TIntV > &CmtyVV, const TStr &OutFNm, const TStr &Desc=TStr())

Detailed Description

Affiliation Graph Model (AGM) graph generator.

Definition at line 19 of file agm.h.

Member Function Documentation

void TAGMUtil::ConnectCmtyVV ( TVec< TIntV > &  CmtyVV, const TIntPrV &  CIDSzPrV, const TIntPrV &  NIDMemPrV, TRnd &  Rnd  )

static

Generate bipartite community affiliation from given power law coefficients for membership distribution and community size distribution.

Definition at line 131 of file agm.cpp.

                                                                                                              {
  const int Nodes = NIDMemPrV.Len(), Coms = CIDSzPrV.Len();
  TIntV NDegV,CDegV;
  TIntPrSet CNIDSet;
  TIntSet HitNodes(Nodes);
  THash<TInt,TIntV> CmtyVH;
  for (int i = 0;i < CIDSzPrV.Len(); i++) {
    for (int j = 0; j < CIDSzPrV[i].Val2; j++) {
      CDegV.Add(CIDSzPrV[i].Val1);
    }
  }
  for (int i = 0; i < NIDMemPrV.Len(); i++) {
    for (int j = 0; j < NIDMemPrV[i].Val2; j++) {
      NDegV.Add(NIDMemPrV[i].Val1);
    }
  }
  while (CDegV.Len() < (int) (1.2 * Nodes)) {
    CDegV.Add(CIDSzPrV[Rnd.GetUniDevInt(Coms)].Val1);
  }
  while (NDegV.Len() < CDegV.Len()) {
    NDegV.Add(NIDMemPrV[Rnd.GetUniDevInt(Nodes)].Val1);
  }
  printf("Total Mem: %d, Total Sz: %d\n",NDegV.Len(), CDegV.Len());
  int c=0;
  while (c++ < 15 && CDegV.Len() > 1) {
    for (int i = 0; i < CDegV.Len(); i++) {
      int u = Rnd.GetUniDevInt(CDegV.Len());
      int v = Rnd.GetUniDevInt(NDegV.Len());
      if (CNIDSet.IsKey(TIntPr(CDegV[u], NDegV[v]))) { continue; }
      CNIDSet.AddKey(TIntPr(CDegV[u], NDegV[v]));
      HitNodes.AddKey(NDegV[v]);
      if (u == CDegV.Len() - 1) { CDegV.DelLast(); }
      else { 
        CDegV[u] = CDegV.Last(); 
        CDegV.DelLast();
      }
      if (v == NDegV.Len() - 1) { NDegV.DelLast(); }
      else { 
        NDegV[v] = NDegV.Last();
        NDegV.DelLast();
      }
    }
  }
  //make sure that every node belongs to at least one community
  for (int i = 0; i < Nodes; i++) {
    int NID = NIDMemPrV[i].Val1;
    if (! HitNodes.IsKey(NID)) {
      CNIDSet.AddKey(TIntPr(CIDSzPrV[Rnd.GetUniDevInt(Coms)].Val1, NID));
      HitNodes.AddKey(NID);
    }
  }
  IAssert(HitNodes.Len() == Nodes);
  for (int i = 0; i < CNIDSet.Len(); i++) {
    TIntPr CNIDPr = CNIDSet[i];
    CmtyVH.AddDat(CNIDPr.Val1);
    CmtyVH.GetDat(CNIDPr.Val1).Add(CNIDPr.Val2);
  }
  CmtyVH.GetDatV(CmtyVV);
}

void TAGMUtil::DumpCmtyVV ( const TStr &  OutFNm, const TVec< TIntV > &  CmtyVV  )

static

dump bipartite community affiliation into a text file

Definition at line 286 of file agm.cpp.

                                                                       {
  FILE* F = fopen(OutFNm.CStr(),"wt");
  for (int i = 0; i < CmtyVV.Len(); i++) {
    for (int j = 0; j < CmtyVV[i].Len(); j++) {
      fprintf(F,"%d\t", (int) CmtyVV[i][j]);
    }
    fprintf(F,"\n");
  }
  fclose(F);
}

void TAGMUtil::DumpCmtyVV ( const TStr  OutFNm, TVec< TIntV > &  CmtyVV, TIntStrH &  NIDNmH  )

static

dump bipartite community affiliation into a text file with node names

Definition at line 298 of file agm.cpp.

                                                                                  {
  FILE* F = fopen(OutFNm.CStr(), "wt");
  for (int c = 0; c < CmtyVV.Len(); c++) {
    for (int u = 0; u < CmtyVV[c].Len(); u++) {
      if (NIDNmH.IsKey(CmtyVV[c][u])){
        fprintf(F, "%s\t", NIDNmH.GetDat(CmtyVV[c][u]).CStr());
      }
      else {
        fprintf(F, "%d\t", (int) CmtyVV[c][u]);
      }
    }
    fprintf(F, "\n");
  }
  fclose(F);
}

int TAGMUtil::FindComsByAGM ( const PUNGraph &  Graph, const int  InitComs, const int  MaxIter, const int  RndSeed, const double  RegGap, const double  PNoCom = 0.0, const TStr  PltFPrx = TStr()  )

static

estimate number of communities using AGM

Definition at line 544 of file agm.cpp.

                                                                                                                                                                         {
  TRnd Rnd(RndSeed);
  int LambdaIter = 100;
  if (Graph->GetNodes() < 200) { LambdaIter = 1; } 
  if (Graph->GetNodes() < 200 && Graph->GetEdges() > 2000) { LambdaIter = 100; } 

  //Find coms with large C
  TAGMFit AGMFitM(Graph, InitComs, RndSeed);
  if (PNoCom > 0.0) { AGMFitM.SetPNoCom(PNoCom); }
  AGMFitM.RunMCMC(MaxIter, LambdaIter, "");

  int TE = Graph->GetEdges();
  TFltV RegV; 
  RegV.Add(0.3 * TE);
  for (int r = 0; r < 25; r++) {
    RegV.Add(RegV.Last() * RegGap);
  }
  TFltPrV RegComsV, RegLV, RegBICV;
  TFltV LV, BICV;
  //record likelihood and number of communities with nonzero P_c
  for (int r = 0; r < RegV.Len(); r++) {
    double RegCoef = RegV[r];
    AGMFitM.SetRegCoef(RegCoef);
    AGMFitM.MLEGradAscentGivenCAG(0.01, 1000);
    AGMFitM.SetRegCoef(0.0);
        
    TVec<TIntV> EstCmtyVV;
    AGMFitM.GetCmtyVV(EstCmtyVV, 0.99);
    int NumLowQ = EstCmtyVV.Len();
    RegComsV.Add(TFltPr(RegCoef, (double) NumLowQ));

    if (EstCmtyVV.Len() > 0) {
      TAGMFit AFTemp(Graph, EstCmtyVV, Rnd);
      AFTemp.MLEGradAscentGivenCAG(0.001, 1000);
      double CurL = AFTemp.Likelihood();
      LV.Add(CurL);
      BICV.Add(-2.0 * CurL + (double) EstCmtyVV.Len() * log((double) Graph->GetNodes() * (Graph->GetNodes() - 1) / 2.0));
    }
    else {
      break;
    }
  }
  // if likelihood does not exist or does not change at all, report the smallest number of communities or 2
  if (LV.Len() == 0) { return 2; }
  else if (LV[0] == LV.Last()) { return (int) TMath::Mx<TFlt>(2.0, RegComsV[LV.Len() - 1].Val2); }


  //normalize likelihood and BIC to 0~100
  int MaxL = 100;
  {
    TFltV& ValueV = LV;
    TFltPrV& RegValueV = RegLV;
    double MinValue = TFlt::Mx, MaxValue = TFlt::Mn;
    for (int l = 0; l < ValueV.Len(); l++) {
      if (ValueV[l] < MinValue) { MinValue = ValueV[l]; }
      if (ValueV[l] > MaxValue) { MaxValue = ValueV[l]; }
    }
    while (ValueV.Len() < RegV.Len()) { ValueV.Add(MinValue); }
    double RangeVal = MaxValue - MinValue;
    for (int l = 0; l < ValueV.Len(); l++) {
      RegValueV.Add(TFltPr(RegV[l], double(MaxL) * (ValueV[l] - MinValue) / RangeVal));
    }
    
  }
  {
    TFltV& ValueV = BICV;
    TFltPrV& RegValueV = RegBICV;
    double MinValue = TFlt::Mx, MaxValue = TFlt::Mn;
    for (int l = 0; l < ValueV.Len(); l++) {
      if (ValueV[l] < MinValue) { MinValue = ValueV[l]; }
      if (ValueV[l] > MaxValue) { MaxValue = ValueV[l]; }
    }
    while (ValueV.Len() < RegV.Len()) { ValueV.Add(MaxValue); }
    double RangeVal = MaxValue - MinValue;
    for (int l = 0; l < ValueV.Len(); l++) {
      RegValueV.Add(TFltPr(RegV[l], double(MaxL) * (ValueV[l] - MinValue) / RangeVal));
    }
  }

  //fit logistic regression to normalized likelihood.
  TVec<TFltV> XV(RegLV.Len());
  TFltV YV (RegLV.Len());
  for (int l = 0; l < RegLV.Len(); l++) {
    XV[l] = TFltV::GetV(log(RegLV[l].Val1));
    YV[l] = RegLV[l].Val2 / (double) MaxL;
  }
  TFltPrV LRVScaled, LRV;
  TLogRegFit LRFit;
  PLogRegPredict LRMd = LRFit.CalcLogRegNewton(XV, YV, PltFPrx);
  for (int l = 0; l < RegLV.Len(); l++) {
    LRV.Add(TFltPr(RegV[l], LRMd->GetCfy(XV[l])));
    LRVScaled.Add(TFltPr(RegV[l], double(MaxL) * LRV.Last().Val2));
  }

  //estimate # communities from fitted logistic regression
  int NumComs = 0, IdxRegDrop = 0;
  double LRThres = 1.1, RegDrop; // 1 / (1 + exp(1.1)) = 0.25
  double LeftReg = 0.0, RightReg = 0.0;
  TFltV Theta;
  LRMd->GetTheta(Theta);
  RegDrop = (- Theta[1] - LRThres) / Theta[0];
  if (RegDrop <= XV[0][0]) { NumComs = (int) RegComsV[0].Val2; }
  else if (RegDrop >= XV.Last()[0]) { NumComs = (int) RegComsV.Last().Val2; }
  else {  //interpolate for RegDrop
    for (int i = 0; i < XV.Len(); i++) {
      if (XV[i][0] > RegDrop) { IdxRegDrop = i; break; }
    }
    
    if (IdxRegDrop == 0) {
      printf("Error!! RegDrop:%f, Theta[0]:%f, Theta[1]:%f\n", RegDrop, Theta[0].Val, Theta[1].Val);
      for (int l = 0; l < RegLV.Len(); l++) {
        printf("X[%d]:%f, Y[%d]:%f\n", l, XV[l][0].Val, l, YV[l].Val);
      }
    }
    IAssert(IdxRegDrop > 0);
    LeftReg = RegDrop - XV[IdxRegDrop - 1][0];
    RightReg = XV[IdxRegDrop][0] - RegDrop;
    NumComs = (int) TMath::Round( (RightReg * RegComsV[IdxRegDrop - 1].Val2 + LeftReg * RegComsV[IdxRegDrop].Val2) / (LeftReg + RightReg));

  }
  //printf("Interpolation coeff: %f, %f, index at drop:%d (%f), Left-Right Vals: %f, %f\n", LeftReg, RightReg, IdxRegDrop, RegDrop, RegComsV[IdxRegDrop - 1].Val2, RegComsV[IdxRegDrop].Val2);
  printf("Num Coms:%d\n", NumComs);
  if (NumComs < 2) { NumComs = 2; }

  if (PltFPrx.Len() > 0) {
    TStr PlotTitle = TStr::Fmt("N:%d, E:%d ", Graph->GetNodes(), TE);
    TGnuPlot GPC(PltFPrx + ".l");
    GPC.AddPlot(RegComsV, gpwLinesPoints, "C");
    GPC.AddPlot(RegLV, gpwLinesPoints, "likelihood");
    GPC.AddPlot(RegBICV, gpwLinesPoints, "BIC");
    GPC.AddPlot(LRVScaled, gpwLinesPoints, "Sigmoid (scaled)");
    GPC.SetScale(gpsLog10X);
    GPC.SetTitle(PlotTitle);
    GPC.SavePng(PltFPrx + ".l.png");
  }
  
  return NumComs;
}

void TAGMUtil::GenCmtyVVFromPL ( TVec< TIntV > &  CmtyVV, const PUNGraph &  Graph, const int &  Nodes, const int &  Coms, const double &  ComSzAlpha, const double &  MemAlpha, const int &  MinSz, const int &  MaxSz, const int &  MinK, const int &  MaxK, TRnd &  Rnd  )

static

Generate bipartite community affiliation from given power law coefficients for membership distribution and community size distribution.

Definition at line 101 of file agm.cpp.

                                                                                                                                                                                                                                              {
  if (Coms == 0 || Nodes == 0) {
    CmtyVV.Clr();
    return;
  }
  TIntV NIDV;
  Graph->GetNIdV(NIDV);
  GenCmtyVVFromPL(CmtyVV, NIDV, Nodes, Coms, ComSzAlpha, MemAlpha, MinSz, MaxSz, MinK, MaxK, Rnd);
}

void TAGMUtil::GenCmtyVVFromPL ( TVec< TIntV > &  CmtyVV, const TIntV &  NIDV, const int &  Nodes, const int &  Coms, const double &  ComSzAlpha, const double &  MemAlpha, const int &  MinSz, const int &  MaxSz, const int &  MinK, const int &  MaxK, TRnd &  Rnd  )

static

Generate bipartite community affiliation from given power law coefficients for membership distribution and community size distribution.

Definition at line 112 of file agm.cpp.

                                                                                                                                                                                                                                          {
  if (Coms == 0 || Nodes == 0) {
    CmtyVV.Clr();
    return;
  }
  TIntV ComSzSeq, MemSeq;
  TAGMUtil::GenPLSeq(ComSzSeq,Coms,ComSzAlpha,Rnd,MinSz,MaxSz);
  TAGMUtil::GenPLSeq(MemSeq,Nodes,MemAlpha,Rnd,MinK,MaxK);
  TIntPrV CIDSzPrV, NIDMemPrV;
  for (int i = 0; i < ComSzSeq.Len(); i++) {
    CIDSzPrV.Add(TIntPr(i, ComSzSeq[i]));
  }
  for (int i = 0; i < MemSeq.Len(); i++) {
    NIDMemPrV.Add(TIntPr(NIDV[i], MemSeq[i]));
  }
  TAGMUtil::ConnectCmtyVV(CmtyVV, CIDSzPrV, NIDMemPrV, Rnd);
}

void TAGMUtil::GenCmtyVVFromPL ( TVec< TIntV > &  CmtyVV, const int &  Nodes, const int &  Coms, const double &  ComSzAlpha, const double &  MemAlpha, const int &  MinSz, const int &  MaxSz, const int &  MinK, const int &  MaxK, TRnd &  Rnd  )

static

Generate bipartite community affiliation from given power law coefficients for membership distribution and community size distribution.

Definition at line 92 of file agm.cpp.

                                                                                                                                                                                                                       {
  TIntV NIDV(Nodes, 0);
  for (int i = 0; i < Nodes; i++) {
    NIDV.Add(i);
  }
  GenCmtyVVFromPL(CmtyVV, NIDV, Nodes, Coms, ComSzAlpha, MemAlpha, MinSz, MaxSz, MinK, MaxK, Rnd);
}

void TAGMUtil::GenPLSeq ( TIntV &  SzSeq, const int &  SeqLen, const double &  Alpha, TRnd &  Rnd, const int &  Min, const int &  Max  )

static

AGMUtil:: Utilities for AGM.

Generate sequence from Power law

Definition at line 81 of file agm.cpp.

                                                                                                                       {
  SzSeq.Gen(SeqLen, 0);
  while (SzSeq.Len() < SeqLen) {
    int Sz = (int) TMath::Round(Rnd.GetPowerDev(Alpha));
    if (Sz >= Min && Sz <= Max) {
      SzSeq.Add(Sz);
    }
  }
}

double TAGMUtil::GetConductance ( const PUNGraph &  Graph, const TIntSet &  CmtyS, const int  Edges  )

static

Definition at line 683 of file agm.cpp.

                                                                                            {
  const int Edges2 = Edges >= 0 ? 2*Edges : Graph->GetEdges();
  int Vol = 0,  Cut = 0; 
  double Phi = 0.0;
  for (int i = 0; i < CmtyS.Len(); i++) {
    if (! Graph->IsNode(CmtyS[i])) { continue; }
    TUNGraph::TNodeI NI = Graph->GetNI(CmtyS[i]);
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      if (! CmtyS.IsKey(NI.GetOutNId(e))) { Cut += 1; }
    }
    Vol += NI.GetOutDeg();
  }
  // get conductance
  if (Vol != Edges2) {
    if (2 * Vol > Edges2) { Phi = Cut / double (Edges2 - Vol); }
    else if (Vol == 0) { Phi = 0.0; }
    else { Phi = Cut / double(Vol); }
  } else {
    if (Vol == Edges2) { Phi = 1.0; }
  }
  return Phi;
}

void TAGMUtil::GetIntersection ( const THashSet< TInt > &  A, const THashSet< TInt > &  B, THashSet< TInt > &  C  )

static

Definition at line 404 of file agm.cpp.

                                                                                                  {
  C.Gen(A.Len());
  if (A.Len() < B.Len()) {
    for (THashSetKeyI<TInt> it = A.BegI(); it < A.EndI(); it++) 
      if (B.IsKey(it.GetKey())) C.AddKey(it.GetKey());
  } else {
    for (THashSetKeyI<TInt> it = B.BegI(); it < B.EndI(); it++) 
      if (A.IsKey(it.GetKey())) C.AddKey(it.GetKey());
  }
}

void TAGMUtil::GetNbhCom ( const PUNGraph &  Graph, const int  NID, TIntSet &  NBCmtyS  )

static

Definition at line 706 of file agm.cpp.

                                                                               {
  TUNGraph::TNodeI NI = Graph->GetNI(NID);
  NBCmtyS.Gen(NI.GetDeg());
  NBCmtyS.AddKey(NID);
  for (int e = 0; e < NI.GetDeg(); e++) {
    NBCmtyS.AddKey(NI.GetNbrNId(e));
  }
}

void TAGMUtil::GetNodeMembership ( THash< TInt, TIntSet > &  NIDComVH, const TVec< TIntV > &  CmtyVV  )

static

get hash table of <Node ID, community IDs which node belongs to>

Definition at line 335 of file agm.cpp.

                                                                                          {
  NIDComVH.Clr();
  for (int i = 0; i < CmtyVV.Len(); i++){
    int CID = i;
    for (int j = 0; j < CmtyVV[i].Len(); j++) {
      int NID = CmtyVV[i][j];
      NIDComVH.AddDat(NID).AddKey(CID);
    }
  }
}

void TAGMUtil::GetNodeMembership ( THash< TInt, TIntSet > &  NIDComVH, const TVec< TIntV > &  CmtyVV, const TIntV &  NIDV  )

static

get hash table of <Node ID, community IDs which node belongs to>. Some nodes in NIDV might belong to no community

Definition at line 347 of file agm.cpp.

                                                                                                             {
  NIDComVH.Clr();
  for (int u = 0; u < NIDV.Len(); u++) {
    NIDComVH.AddDat(NIDV[u]);
  }
  for (int i = 0; i < CmtyVV.Len(); i++){
    int CID = i;
    for (int j = 0; j < CmtyVV[i].Len(); j++) {
      int NID = CmtyVV[i][j];
      NIDComVH.AddDat(NID).AddKey(CID);
    }
  }
}

void TAGMUtil::GetNodeMembership ( TIntH &  NIDComVH, const THash< TInt, TIntV > &  CmtyVH  )

static

get hash table of <Node ID, membership size>

Definition at line 324 of file agm.cpp.

                                                                                  {
  NIDComVH.Clr();
  for (THash<TInt,TIntV>::TIter HI = CmtyVH.BegI(); HI < CmtyVH.EndI(); HI++){
    for (int j = 0;j < HI.GetDat().Len(); j++) {
      int NID = HI.GetDat()[j];
      NIDComVH.AddDat(NID)++;
    }
  }
}

void TAGMUtil::GetNodeMembership ( THash< TInt, TIntSet > &  NIDComVH, const TVec< TIntSet > &  CmtyVV  )

static

Definition at line 362 of file agm.cpp.

                                                                                            {
  for (int i = 0; i < CmtyVV.Len(); i++){
    int CID = i;
    for (TIntSet::TIter SI = CmtyVV[i].BegI(); SI < CmtyVV[i].EndI(); SI++) {
      int NID = SI.GetKey();
      NIDComVH.AddDat(NID).AddKey(CID);
    }
  }
}

void TAGMUtil::GetNodeMembership ( THash< TInt, TIntSet > &  NIDComVH, const THash< TInt, TIntV > &  CmtyVH  )

static

Definition at line 371 of file agm.cpp.

                                                                                                {
  for (THash<TInt,TIntV>::TIter HI = CmtyVH.BegI(); HI < CmtyVH.EndI(); HI++){
    int CID = HI.GetKey();
    for (int j = 0; j < HI.GetDat().Len(); j++) {
      int NID = HI.GetDat()[j];
      NIDComVH.AddDat(NID).AddKey(CID);
    }
  }
}

void TAGMUtil::GetNodeMembership ( THash< TInt, TIntV > &  NIDComVH, const THash< TInt, TIntV > &  CmtyVH  )

static

Definition at line 381 of file agm.cpp.

                                                                                              {
  for (int i = 0; i < CmtyVH.Len(); i++){
    int CID = CmtyVH.GetKey(i);
    for (int j = 0; j < CmtyVH[i].Len(); j++) {
      int NID = CmtyVH[i][j];
      NIDComVH.AddDat(NID).Add(CID);
    }
  }
}

void TAGMUtil::GetNodeMembership ( THash< TInt, TIntV > &  NIDComVH, const TVec< TIntV > &  CmtyVV  )

static

Definition at line 391 of file agm.cpp.

                                                                                        {
  THash<TInt,TIntV> CmtyVH;
  for (int i = 0; i < CmtyVV.Len(); i++) {
    CmtyVH.AddDat(i, CmtyVV[i]);
  }
  GetNodeMembership(NIDComVH, CmtyVH);
}

template<class PGraph >

static void TAGMUtil::GVizComGraph ( const PGraph &  Graph, const TVec< TIntV > &  CmtyVV, const TStr &  OutFNm, const TStr &  Desc = TStr()  )

inlinestatic

Definition at line 105 of file agm.h.

                                                                                                                         {
    TStrV Colors = TStrV::GetV("red","blue","green","pink","cyan");
    TStrV Shapes = TStrV::GetV("ellipse","triangle","square","pentagon","hexagon");
    THash<TInt,TIntV> NIDComVH;
    GetNodeMembership(NIDComVH,CmtyVV);

    const TStr Ext = OutFNm.GetFExt();
    const TStr GraphFNm = OutFNm.GetSubStr(0, OutFNm.Len() - Ext.Len()) + "dot";
    const bool IsDir = HasGraphFlag(typename PGraph::TObj, gfDirected);
    FILE *F = fopen(GraphFNm.CStr(), "wt");
    if (! Desc.Empty()) fprintf(F, "/*****\n%s\n*****/\n\n", Desc.CStr());
    if (IsDir) { fprintf(F, "digraph G {\n"); } else { fprintf(F, "graph G {\n"); }
    fprintf(F, "  graph [splines=false overlap=false]\n"); //size=\"12,10\" ratio=fill
    fprintf(F, "  node  [width=0.3, height=0.3]\n");
    //nodes
    for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
      int NID = NI.GetId();
      TIntV& CIDV = NIDComVH.GetDat(NID);
      IAssert(CIDV.Len()>0);
      TStr ShapeNm = Shapes[(CIDV.Len()-1) % Shapes.Len()];
      TStr ColorNm = Colors[CIDV[0] % Colors.Len()];
      TStr NodeComLabel = TStr::Fmt("%d(",NID);
      for(int i=0;i<CIDV.Len();i++) {
        TStr TmpStr = TStr::Fmt("%d",int(CIDV[i]));
        NodeComLabel += TmpStr;
        if(i<CIDV.Len()-1){NodeComLabel+=",";}
      }
      NodeComLabel += ")";
      fprintf(F, "  %d [style=filled, shape=\"%s\" fillcolor=\"%s\" label=\"%s\"];\n", NI.GetId(), ShapeNm.CStr(),ColorNm.CStr(), NodeComLabel.CStr()); 
    }
  
    // edges
    for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
      if (NI.GetOutDeg()==0 && NI.GetInDeg()==0  ) { 
        fprintf(F, "%d;\n", NI.GetId()); }
      else {
        for (int e = 0; e < NI.GetOutDeg(); e++) {
          if (! IsDir && NI.GetId() > NI.GetOutNId(e)) { continue; }
          fprintf(F, "  %d %s %d;\n", NI.GetId(), IsDir?"->":"--", NI.GetOutNId(e)); 
        }
      }
    }
    if (! Desc.Empty()) {
      fprintf(F, "  label = \"\\n%s\\n\";", Desc.CStr());
      fprintf(F, "  fontsize=24;\n");
    }
    fprintf(F, "}\n");
    fclose(F);
    TSnap::TSnapDetail::GVizDoLayout(GraphFNm, OutFNm, gvlNeato);
  }

int TAGMUtil::Intersection ( const TIntV &  C1, const TIntV &  C2  )

static

Definition at line 399 of file agm.cpp.

                                                           {
  TIntSet S1(C1), S2(C2);
  return TAGMUtil::Intersection(S1, S2);
}

int TAGMUtil::Intersection ( const THashSet< TInt > &  A, const THashSet< TInt > &  B  )

static

Definition at line 415 of file agm.cpp.

                                                                           {
  int n = 0;
  if (A.Len() < B.Len()) {
    for (THashSetKeyI<TInt> it = A.BegI(); it < A.EndI(); it++) 
      if (B.IsKey(it.GetKey())) n++;
  } else {
    for (THashSetKeyI<TInt> it = B.BegI(); it < B.EndI(); it++) 
      if (A.IsKey(it.GetKey())) n++;
  }
  return n;
}

void TAGMUtil::LoadCmtyVV ( const TStr &  InFNm, TVec< TIntV > &  CmtyVV  )

static

load bipartite community affiliation graph from text file (each row contains the member node IDs for each community)

Definition at line 246 of file agm.cpp.

                                                                {
  CmtyVV.Gen(Kilo(100), 0);
  TSsParser Ss(InFNm, ssfWhiteSep);
  while (Ss.Next()) {
    if(Ss.GetFlds() > 0) {
      TIntV CmtyV;
      for (int i = 0; i < Ss.GetFlds(); i++) {
        if (Ss.IsInt(i)) {
          CmtyV.Add(Ss.GetInt(i));
        }
      }
      CmtyVV.Add(CmtyV);
    }
  }
  CmtyVV.Pack();
  printf("community loading completed (%d communities)\n",CmtyVV.Len());

}

void TAGMUtil::LoadCmtyVV ( const TStr &  InFNm, TVec< TIntV > &  CmtyVV, TStrHash< TInt > &  StrToNIdH, const int  BeginCol, const int  MinSz = 3, const TSsFmt  Sep = ssfTabSep  )

static

load bipartite community affiliation graph from text file (each row contains the member node IDs for each community)

Definition at line 266 of file agm.cpp.

                                                                                                                                                  {
  CmtyVV.Gen(Kilo(100), 0);
  TSsParser Ss(InFNm, Sep);
  while (Ss.Next()) {
    if(Ss.GetFlds() > BeginCol) {
      TIntV CmtyV;
      for (int i = BeginCol; i < Ss.GetFlds(); i++) {
        if (StrToNIdH.IsKey(Ss.GetFld(i))) {
          CmtyV.Add(StrToNIdH.GetKeyId(Ss.GetFld(i)));
        }
      }
      if (CmtyV.Len() < MinSz) { continue; }
      CmtyVV.Add(CmtyV);
    }
  }
  CmtyVV.Pack();
  printf("community loading completed (%d communities)\n",CmtyVV.Len());
}

template<class PGraph >

static PGraph TAGMUtil::LoadEdgeListStr ( const TStr &  InFNm, TIntStrH &  NIDNameH, const int &  SrcColId = 0, const int &  DstColId = 1, const TSsFmt  SsFmt = ssfTabSep  )

inlinestatic

Definition at line 67 of file agm.h.

                                                                                                                                                         {
    TSsParser Ss(InFNm, SsFmt);
    PGraph Graph = PGraph::TObj::New();
    TStrHash<TInt> StrSet(Mega(1), true);
    while (Ss.Next()) {
      const int SrcNId = StrSet.AddKey(Ss[SrcColId]);
      const int DstNId = StrSet.AddKey(Ss[DstColId]);
      if (! Graph->IsNode(SrcNId)) { Graph->AddNode(SrcNId); }
      if (! Graph->IsNode(DstNId)) { Graph->AddNode(DstNId); }
      Graph->AddEdge(SrcNId, DstNId);
    }
    NIDNameH.Gen(StrSet.Len());
    for (int s = 0; s < StrSet.Len(); s++) { NIDNameH.AddDat(s, StrSet.GetKey(s)); }
    IAssert(NIDNameH.Len() == Graph->GetNodes());

    Graph->Defrag();
    return Graph;
  }

template<class PGraph >

static PGraph TAGMUtil::LoadEdgeListStr ( const TStr &  InFNm, TStrHash< TInt > &  NodeNameH, const int &  SrcColId = 0, const int &  DstColId = 1, const TSsFmt  SsFmt = ssfTabSep  )

inlinestatic

Definition at line 86 of file agm.h.

                                                                                                                                                                {
    TSsParser Ss(InFNm, SsFmt);
    PGraph Graph = PGraph::TObj::New();
    TStrHash<TInt> StrSet(Mega(1), true);
    while (Ss.Next()) {
      const int SrcNId = StrSet.AddKey(Ss[SrcColId]);
      const int DstNId = StrSet.AddKey(Ss[DstColId]);
      if (! Graph->IsNode(SrcNId)) { Graph->AddNode(SrcNId); }
      if (! Graph->IsNode(DstNId)) { Graph->AddNode(DstNId); }
      Graph->AddEdge(SrcNId, DstNId);
    }
    NodeNameH = StrSet;
    NodeNameH.Pack();

    Graph->Defrag();
    return Graph;
  }

void TAGMUtil::RewireCmtyNID ( THash< TInt, TIntV > &  CmtyVH, TRnd &  Rnd  )

static

rewire bipartite community affiliation graphs

Definition at line 202 of file agm.cpp.

                                                                  {
  THash<TInt,TIntV > NewCmtyVH(CmtyVH.Len());
  TIntV NDegV;
  TIntV CDegV;
  for (int i = 0; i < CmtyVH.Len(); i++) {
    int CID = CmtyVH.GetKey(i);
    for (int j = 0; j < CmtyVH[i].Len(); j++) {
      int NID = CmtyVH[i][j];
      NDegV.Add(NID);
      CDegV.Add(CID);
    }
  }
  TIntPrSet CNIDSet(CDegV.Len());
  int c=0;
  while (c++ < 15 && CDegV.Len() > 1){
    for (int i = 0; i < CDegV.Len(); i++) {
      int u = Rnd.GetUniDevInt(CDegV.Len());
      int v = Rnd.GetUniDevInt(NDegV.Len());
      if (CNIDSet.IsKey(TIntPr(CDegV[u], NDegV[v]))) { continue; }
      CNIDSet.AddKey(TIntPr(CDegV[u], NDegV[v]));
      if (u == CDegV.Len() - 1) { 
        CDegV.DelLast(); 
      }  else {
        CDegV[u] = CDegV.Last();
        CDegV.DelLast();
      }
      if ( v == NDegV.Len() - 1) {
        NDegV.DelLast();
      }  else{
        NDegV[v] = NDegV.Last();
        NDegV.DelLast();
      }
    }
  }
  for (int i = 0; i < CNIDSet.Len(); i++) {
    TIntPr CNIDPr = CNIDSet[i];
    IAssert(CmtyVH.IsKey(CNIDPr.Val1));
    NewCmtyVH.AddDat(CNIDPr.Val1);
    NewCmtyVH.GetDat(CNIDPr.Val1).Add(CNIDPr.Val2);
  }
  CmtyVH = NewCmtyVH;
}

void TAGMUtil::RewireCmtyVV ( const TVec< TIntV > &  CmtyVVIn, TVec< TIntV > &  CmtyVVOut, TRnd &  Rnd  )

static

rewire bipartite community affiliation graphs

Definition at line 192 of file agm.cpp.

                                                                                         {
  THash<TInt,TIntV> CmtyVH;
  for (int i = 0; i < CmtyVVIn.Len(); i++) {
    CmtyVH.AddDat(i, CmtyVVIn[i]);
  }
  TAGMUtil::RewireCmtyNID(CmtyVH, Rnd);
  CmtyVH.GetDatV(CmtyVVOut);
}

void TAGMUtil::SaveBipartiteGephi ( const TStr &  OutFNm, const TIntV &  NIDV, const TVec< TIntV > &  CmtyVV, const double  MaxSz, const double  MinSz, const TIntStrH &  NIDNameH, const THash< TInt, TIntTr > &  NIDColorH, const THash< TInt, TIntTr > &  CIDColorH  )

static

save bipartite community affiliation into gexf file

Plot bipartite graph

Definition at line 486 of file agm.cpp.

                                                                                                                                                                                                                                                 {
  if (CmtyVV.Len() == 0) { return; }
  double NXMin = 0.1, YMin = 0.1, NXMax = 250.00, YMax = 30.0;
  double CXMin = 0.3 * NXMax, CXMax = 0.7 * NXMax;
  double CStep = (CXMax - CXMin) / (double) CmtyVV.Len(), NStep = (NXMax - NXMin) / (double) NIDV.Len();
  THash<TInt,TIntV> NIDComVH;
  TAGMUtil::GetNodeMembership(NIDComVH, CmtyVV);

  FILE* F = fopen(OutFNm.CStr(), "wt");
  fprintf(F, "<?xml version='1.0' encoding='UTF-8'?>\n");
  fprintf(F, "<gexf xmlns='http://www.gexf.net/1.2draft' xmlns:viz='http://www.gexf.net/1.1draft/viz' xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xsi:schemaLocation='http://www.gexf.net/1.2draft http://www.gexf.net/1.2draft/gexf.xsd' version='1.2'>\n");
  fprintf(F, "\t<graph mode='static' defaultedgetype='directed'>\n");
  fprintf(F, "\t\t<nodes>\n");
  for (int c = 0; c < CmtyVV.Len(); c++) {
    int CID = c;
    double XPos = c * CStep + CXMin;
    TIntTr Color = CIDColorH.IsKey(CID)? CIDColorH.GetDat(CID) : TIntTr(120, 120, 120);
    fprintf(F, "\t\t\t<node id='C%d' label='C%d'>\n", CID, CID);
    fprintf(F, "\t\t\t\t<viz:color r='%d' g='%d' b='%d'/>\n", Color.Val1.Val, Color.Val2.Val, Color.Val3.Val);
    fprintf(F, "\t\t\t\t<viz:size value='%.3f'/>\n", MaxSz);
    fprintf(F, "\t\t\t\t<viz:shape value='square'/>\n");
    fprintf(F, "\t\t\t\t<viz:position x='%f' y='%f' z='0.0'/>\n", XPos, YMax); 
    fprintf(F, "\t\t\t</node>\n");
  }

  for (int u = 0;u < NIDV.Len(); u++) {
    int NID = NIDV[u];
    TStr Label = NIDNameH.IsKey(NID)? NIDNameH.GetDat(NID): "";
    double Size = MinSz;
    double XPos = NXMin + u * NStep;
    TIntTr Color = NIDColorH.IsKey(NID)? NIDColorH.GetDat(NID) : TIntTr(120, 120, 120);
    double Alpha = 1.0;
    fprintf(F, "\t\t\t<node id='%d' label='%s'>\n", NID, Label.CStr());
    fprintf(F, "\t\t\t\t<viz:color r='%d' g='%d' b='%d' a='%.1f'/>\n", Color.Val1.Val, Color.Val2.Val, Color.Val3.Val, Alpha);
    fprintf(F, "\t\t\t\t<viz:size value='%.3f'/>\n", Size);
    fprintf(F, "\t\t\t\t<viz:shape value='square'/>\n");
    fprintf(F, "\t\t\t\t<viz:position x='%f' y='%f' z='0.0'/>\n", XPos, YMin); 
    fprintf(F, "\t\t\t</node>\n");
  }
  fprintf(F, "\t\t</nodes>\n");
  fprintf(F, "\t\t<edges>\n");
  int EID = 0;
  for (int u = 0;u < NIDV.Len(); u++) {
    int NID = NIDV[u];
    if (NIDComVH.IsKey(NID)) {
      for (int c = 0; c < NIDComVH.GetDat(NID).Len(); c++) {
        int CID = NIDComVH.GetDat(NID)[c];
        fprintf(F, "\t\t\t<edge id='%d' source='C%d' target='%d'/>\n", EID++, CID, NID);
      }
    }
  }
  fprintf(F, "\t\t</edges>\n");
  fprintf(F, "\t</graph>\n");
  fprintf(F, "</gexf>\n");
}

static void TAGMUtil::SaveGephi ( const TStr &  OutFNm, const PUNGraph &  G, const TVec< TIntV > &  CmtyVVAtr, const double  MaxSz, const double  MinSz  )

inlinestatic

Definition at line 55 of file agm.h.

                                                                                                                                      {
    THash<TInt, TStr> TmpH;
    SaveGephi(OutFNm, G, CmtyVVAtr, MaxSz, MinSz, TmpH);
  }

static void TAGMUtil::SaveGephi ( const TStr &  OutFNm, const PUNGraph &  G, const TVec< TIntV > &  CmtyVVAtr, const double  MaxSz, const double  MinSz, const THash< TInt, TStr > &  NIDNameH  )

inlinestatic

Definition at line 59 of file agm.h.

                                                                                                                                                                         { 
    THash<TInt, TIntTr> TmpH; 
    SaveGephi(OutFNm, G, CmtyVVAtr, MaxSz, MinSz, NIDNameH, TmpH);
  }

void TAGMUtil::SaveGephi ( const TStr &  OutFNm, const PUNGraph &  G, const TVec< TIntV > &  CmtyVVAtr, const double  MaxSz, const double  MinSz, const THash< TInt, TStr > &  NIDNameH, const THash< TInt, TIntTr > &  NIDColorH  )

static

save graph into a gexf file which Gephi can read

Definition at line 428 of file agm.cpp.

                                                                                                                                                                                                     {
  THash<TInt,TIntV> NIDComVHAtr;
  TAGMUtil::GetNodeMembership(NIDComVHAtr, CmtyVVAtr);

  FILE* F = fopen(OutFNm.CStr(), "wt");
  fprintf(F, "<?xml version='1.0' encoding='UTF-8'?>\n");
  fprintf(F, "<gexf xmlns='http://www.gexf.net/1.2draft' xmlns:viz='http://www.gexf.net/1.1draft/viz' xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xsi:schemaLocation='http://www.gexf.net/1.2draft http://www.gexf.net/1.2draft/gexf.xsd' version='1.2'>\n");
  fprintf(F, "\t<graph mode='static' defaultedgetype='undirected'>\n");
  if (CmtyVVAtr.Len() > 0) {
    fprintf(F, "\t<attributes class='node'>\n");
    for (int c = 0; c < CmtyVVAtr.Len(); c++) {
      fprintf(F, "\t\t<attribute id='%d' title='c%d' type='boolean'>", c, c);
      fprintf(F, "\t\t<default>false</default>\n");
      fprintf(F, "\t\t</attribute>\n");
    }
    fprintf(F, "\t</attributes>\n");
  }
  fprintf(F, "\t\t<nodes>\n");
  for (TUNGraph::TNodeI NI = G->BegNI(); NI < G->EndNI(); NI++) {
    int NID = NI.GetId();
    TStr Label = NIDNameH.IsKey(NID)? NIDNameH.GetDat(NID): "";
    TIntTr Color = NIDColorH.IsKey(NID)? NIDColorH.GetDat(NID) : TIntTr(120, 120, 120);

    double Size = MinSz;
    double SizeStep = (MaxSz - MinSz) / (double) CmtyVVAtr.Len();
    if (NIDComVHAtr.IsKey(NID)) {
      Size = MinSz +  SizeStep *  (double) NIDComVHAtr.GetDat(NID).Len();
    }
    double Alpha = 1.0;
    fprintf(F, "\t\t\t<node id='%d' label='%s'>\n", NID, Label.CStr());
    fprintf(F, "\t\t\t\t<viz:color r='%d' g='%d' b='%d' a='%.1f'/>\n", Color.Val1.Val, Color.Val2.Val, Color.Val3.Val, Alpha);
    fprintf(F, "\t\t\t\t<viz:size value='%.3f'/>\n", Size);
    //specify attributes
    if (NIDComVHAtr.IsKey(NID)) {
      fprintf(F, "\t\t\t\t<attvalues>\n");
      for (int c = 0; c < NIDComVHAtr.GetDat(NID).Len(); c++) {
        int CID = NIDComVHAtr.GetDat(NID)[c];
        fprintf(F, "\t\t\t\t\t<attvalue for='%d' value='true'/>\n", CID);
      }
      fprintf(F, "\t\t\t\t</attvalues>\n");
    }

    fprintf(F, "\t\t\t</node>\n");
  }
  fprintf(F, "\t\t</nodes>\n");
  //plot edges
  int EID = 0;
  fprintf(F, "\t\t<edges>\n");
  for (TUNGraph::TEdgeI EI = G->BegEI(); EI < G->EndEI(); EI++) {
    fprintf(F, "\t\t\t<edge id='%d' source='%d' target='%d'/>\n", EID++, EI.GetSrcNId(), EI.GetDstNId());
  }
  fprintf(F, "\t\t</edges>\n");
  fprintf(F, "\t</graph>\n");
  fprintf(F, "</gexf>\n");
  fclose(F);
}

int TAGMUtil::TotalMemberships ( const TVec< TIntV > &  CmtyVV )

static

total number of memberships (== sum of the sizes of communities)

Definition at line 315 of file agm.cpp.

                                                       {
  int M = 0;
  for (int i = 0; i < CmtyVV.Len(); i++) {
    M += CmtyVV[i].Len();
  }
  return M;
}

---

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

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