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
Static Public Member Functions | List of all members
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.

131  {
132  const int Nodes = NIDMemPrV.Len(), Coms = CIDSzPrV.Len();
133  TIntV NDegV,CDegV;
134  TIntPrSet CNIDSet;
135  TIntSet HitNodes(Nodes);
136  THash<TInt,TIntV> CmtyVH;
137  for (int i = 0;i < CIDSzPrV.Len(); i++) {
138  for (int j = 0; j < CIDSzPrV[i].Val2; j++) {
139  CDegV.Add(CIDSzPrV[i].Val1);
140  }
141  }
142  for (int i = 0; i < NIDMemPrV.Len(); i++) {
143  for (int j = 0; j < NIDMemPrV[i].Val2; j++) {
144  NDegV.Add(NIDMemPrV[i].Val1);
145  }
146  }
147  while (CDegV.Len() < (int) (1.2 * Nodes)) {
148  CDegV.Add(CIDSzPrV[Rnd.GetUniDevInt(Coms)].Val1);
149  }
150  while (NDegV.Len() < CDegV.Len()) {
151  NDegV.Add(NIDMemPrV[Rnd.GetUniDevInt(Nodes)].Val1);
152  }
153  printf("Total Mem: %d, Total Sz: %d\n",NDegV.Len(), CDegV.Len());
154  int c=0;
155  while (c++ < 15 && CDegV.Len() > 1) {
156  for (int i = 0; i < CDegV.Len(); i++) {
157  int u = Rnd.GetUniDevInt(CDegV.Len());
158  int v = Rnd.GetUniDevInt(NDegV.Len());
159  if (CNIDSet.IsKey(TIntPr(CDegV[u], NDegV[v]))) { continue; }
160  CNIDSet.AddKey(TIntPr(CDegV[u], NDegV[v]));
161  HitNodes.AddKey(NDegV[v]);
162  if (u == CDegV.Len() - 1) { CDegV.DelLast(); }
163  else {
164  CDegV[u] = CDegV.Last();
165  CDegV.DelLast();
166  }
167  if (v == NDegV.Len() - 1) { NDegV.DelLast(); }
168  else {
169  NDegV[v] = NDegV.Last();
170  NDegV.DelLast();
171  }
172  }
173  }
174  //make sure that every node belongs to at least one community
175  for (int i = 0; i < Nodes; i++) {
176  int NID = NIDMemPrV[i].Val1;
177  if (! HitNodes.IsKey(NID)) {
178  CNIDSet.AddKey(TIntPr(CIDSzPrV[Rnd.GetUniDevInt(Coms)].Val1, NID));
179  HitNodes.AddKey(NID);
180  }
181  }
182  IAssert(HitNodes.Len() == Nodes);
183  for (int i = 0; i < CNIDSet.Len(); i++) {
184  TIntPr CNIDPr = CNIDSet[i];
185  CmtyVH.AddDat(CNIDPr.Val1);
186  CmtyVH.GetDat(CNIDPr.Val1).Add(CNIDPr.Val2);
187  }
188  CmtyVH.GetDatV(CmtyVV);
189 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
THash::GetDatV
void GetDatV(TVec< TDat > &DatV) const
Definition: hash.h:492
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
THashSet::Len
int Len() const
Definition: shash.h:1121
TPair
Definition: ds.h:32
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TPair::Val2
TVal2 Val2
Definition: ds.h:35
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVec::DelLast
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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.

286  {
287  FILE* F = fopen(OutFNm.CStr(),"wt");
288  for (int i = 0; i < CmtyVV.Len(); i++) {
289  for (int j = 0; j < CmtyVV[i].Len(); j++) {
290  fprintf(F,"%d\t", (int) CmtyVV[i][j]);
291  }
292  fprintf(F,"\n");
293  }
294  fclose(F);
295 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TStr::CStr
char * CStr()
Definition: dt.h:479
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.

298  {
299  FILE* F = fopen(OutFNm.CStr(), "wt");
300  for (int c = 0; c < CmtyVV.Len(); c++) {
301  for (int u = 0; u < CmtyVV[c].Len(); u++) {
302  if (NIDNmH.IsKey(CmtyVV[c][u])){
303  fprintf(F, "%s\t", NIDNmH.GetDat(CmtyVV[c][u]).CStr());
304  }
305  else {
306  fprintf(F, "%d\t", (int) CmtyVV[c][u]);
307  }
308  }
309  fprintf(F, "\n");
310  }
311  fclose(F);
312 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TStr::CStr
char * CStr()
Definition: dt.h:479
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
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.

544  {
545  TRnd Rnd(RndSeed);
546  int LambdaIter = 100;
547  if (Graph->GetNodes() < 200) { LambdaIter = 1; }
548  if (Graph->GetNodes() < 200 && Graph->GetEdges() > 2000) { LambdaIter = 100; }
549 
550  //Find coms with large C
551  TAGMFit AGMFitM(Graph, InitComs, RndSeed);
552  if (PNoCom > 0.0) { AGMFitM.SetPNoCom(PNoCom); }
553  AGMFitM.RunMCMC(MaxIter, LambdaIter, "");
554 
555  int TE = Graph->GetEdges();
556  TFltV RegV;
557  RegV.Add(0.3 * TE);
558  for (int r = 0; r < 25; r++) {
559  RegV.Add(RegV.Last() * RegGap);
560  }
561  TFltPrV RegComsV, RegLV, RegBICV;
562  TFltV LV, BICV;
563  //record likelihood and number of communities with nonzero P_c
564  for (int r = 0; r < RegV.Len(); r++) {
565  double RegCoef = RegV[r];
566  AGMFitM.SetRegCoef(RegCoef);
567  AGMFitM.MLEGradAscentGivenCAG(0.01, 1000);
568  AGMFitM.SetRegCoef(0.0);
569 
570  TVec<TIntV> EstCmtyVV;
571  AGMFitM.GetCmtyVV(EstCmtyVV, 0.99);
572  int NumLowQ = EstCmtyVV.Len();
573  RegComsV.Add(TFltPr(RegCoef, (double) NumLowQ));
574 
575  if (EstCmtyVV.Len() > 0) {
576  TAGMFit AFTemp(Graph, EstCmtyVV, Rnd);
577  AFTemp.MLEGradAscentGivenCAG(0.001, 1000);
578  double CurL = AFTemp.Likelihood();
579  LV.Add(CurL);
580  BICV.Add(-2.0 * CurL + (double) EstCmtyVV.Len() * log((double) Graph->GetNodes() * (Graph->GetNodes() - 1) / 2.0));
581  }
582  else {
583  break;
584  }
585  }
586  // if likelihood does not exist or does not change at all, report the smallest number of communities or 2
587  if (LV.Len() == 0) { return 2; }
588  else if (LV[0] == LV.Last()) { return (int) TMath::Mx<TFlt>(2.0, RegComsV[LV.Len() - 1].Val2); }
589 
590 
591  //normalize likelihood and BIC to 0~100
592  int MaxL = 100;
593  {
594  TFltV& ValueV = LV;
595  TFltPrV& RegValueV = RegLV;
596  double MinValue = TFlt::Mx, MaxValue = TFlt::Mn;
597  for (int l = 0; l < ValueV.Len(); l++) {
598  if (ValueV[l] < MinValue) { MinValue = ValueV[l]; }
599  if (ValueV[l] > MaxValue) { MaxValue = ValueV[l]; }
600  }
601  while (ValueV.Len() < RegV.Len()) { ValueV.Add(MinValue); }
602  double RangeVal = MaxValue - MinValue;
603  for (int l = 0; l < ValueV.Len(); l++) {
604  RegValueV.Add(TFltPr(RegV[l], double(MaxL) * (ValueV[l] - MinValue) / RangeVal));
605  }
606 
607  }
608  {
609  TFltV& ValueV = BICV;
610  TFltPrV& RegValueV = RegBICV;
611  double MinValue = TFlt::Mx, MaxValue = TFlt::Mn;
612  for (int l = 0; l < ValueV.Len(); l++) {
613  if (ValueV[l] < MinValue) { MinValue = ValueV[l]; }
614  if (ValueV[l] > MaxValue) { MaxValue = ValueV[l]; }
615  }
616  while (ValueV.Len() < RegV.Len()) { ValueV.Add(MaxValue); }
617  double RangeVal = MaxValue - MinValue;
618  for (int l = 0; l < ValueV.Len(); l++) {
619  RegValueV.Add(TFltPr(RegV[l], double(MaxL) * (ValueV[l] - MinValue) / RangeVal));
620  }
621  }
622 
623  //fit logistic regression to normalized likelihood.
624  TVec<TFltV> XV(RegLV.Len());
625  TFltV YV (RegLV.Len());
626  for (int l = 0; l < RegLV.Len(); l++) {
627  XV[l] = TFltV::GetV(log(RegLV[l].Val1));
628  YV[l] = RegLV[l].Val2 / (double) MaxL;
629  }
630  TFltPrV LRVScaled, LRV;
631  TLogRegFit LRFit;
632  PLogRegPredict LRMd = LRFit.CalcLogRegNewton(XV, YV, PltFPrx);
633  for (int l = 0; l < RegLV.Len(); l++) {
634  LRV.Add(TFltPr(RegV[l], LRMd->GetCfy(XV[l])));
635  LRVScaled.Add(TFltPr(RegV[l], double(MaxL) * LRV.Last().Val2));
636  }
637 
638  //estimate # communities from fitted logistic regression
639  int NumComs = 0, IdxRegDrop = 0;
640  double LRThres = 1.1, RegDrop; // 1 / (1 + exp(1.1)) = 0.25
641  double LeftReg = 0.0, RightReg = 0.0;
642  TFltV Theta;
643  LRMd->GetTheta(Theta);
644  RegDrop = (- Theta[1] - LRThres) / Theta[0];
645  if (RegDrop <= XV[0][0]) { NumComs = (int) RegComsV[0].Val2; }
646  else if (RegDrop >= XV.Last()[0]) { NumComs = (int) RegComsV.Last().Val2; }
647  else { //interpolate for RegDrop
648  for (int i = 0; i < XV.Len(); i++) {
649  if (XV[i][0] > RegDrop) { IdxRegDrop = i; break; }
650  }
651 
652  if (IdxRegDrop == 0) {
653  printf("Error!! RegDrop:%f, Theta[0]:%f, Theta[1]:%f\n", RegDrop, Theta[0].Val, Theta[1].Val);
654  for (int l = 0; l < RegLV.Len(); l++) {
655  printf("X[%d]:%f, Y[%d]:%f\n", l, XV[l][0].Val, l, YV[l].Val);
656  }
657  }
658  IAssert(IdxRegDrop > 0);
659  LeftReg = RegDrop - XV[IdxRegDrop - 1][0];
660  RightReg = XV[IdxRegDrop][0] - RegDrop;
661  NumComs = (int) TMath::Round( (RightReg * RegComsV[IdxRegDrop - 1].Val2 + LeftReg * RegComsV[IdxRegDrop].Val2) / (LeftReg + RightReg));
662 
663  }
664  //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);
665  printf("Num Coms:%d\n", NumComs);
666  if (NumComs < 2) { NumComs = 2; }
667 
668  if (PltFPrx.Len() > 0) {
669  TStr PlotTitle = TStr::Fmt("N:%d, E:%d ", Graph->GetNodes(), TE);
670  TGnuPlot GPC(PltFPrx + ".l");
671  GPC.AddPlot(RegComsV, gpwLinesPoints, "C");
672  GPC.AddPlot(RegLV, gpwLinesPoints, "likelihood");
673  GPC.AddPlot(RegBICV, gpwLinesPoints, "BIC");
674  GPC.AddPlot(LRVScaled, gpwLinesPoints, "Sigmoid (scaled)");
675  GPC.SetScale(gpsLog10X);
676  GPC.SetTitle(PlotTitle);
677  GPC.SavePng(PltFPrx + ".l.png");
678  }
679 
680  return NumComs;
681 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TStr::Len
int Len() const
Definition: dt.h:490
TRnd
Definition: dt.h:11
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TAGMFit
Fitting the Affilialiton Graph Model (AGM).
Definition: agmfit.h:8
TFlt::Mx
static const double Mx
Definition: dt.h:1391
TLogRegFit::CalcLogRegNewton
PLogRegPredict CalcLogRegNewton(const TVec< TFltV > &XPt, const TFltV &yPt, const TStr &PlotNm=TStr(), const double &ChangeEps=0.01, const int &MaxStep=200, const bool InterceptPt=false)
Definition: agm.cpp:882
TMath::Round
static double Round(const double &Val)
Definition: xmath.h:16
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
TFltPr
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TStr
Definition: dt.h:412
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TPt
Definition: bd.h:196
TVec< TFlt >::GetV
static TVec< TFlt, int > GetV(const TFlt &Val1)
Returns a vector on element Val1.
Definition: ds.h:848
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TFlt::Mn
static const double Mn
Definition: dt.h:1390
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.

101  {
102  if (Coms == 0 || Nodes == 0) {
103  CmtyVV.Clr();
104  return;
105  }
106  TIntV NIDV;
107  Graph->GetNIdV(NIDV);
108  GenCmtyVVFromPL(CmtyVV, NIDV, Nodes, Coms, ComSzAlpha, MemAlpha, MinSz, MaxSz, MinK, MaxK, Rnd);
109 }
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TAGMUtil::GenCmtyVVFromPL
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 distributio...
Definition: agm.cpp:101
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.

112  {
113  if (Coms == 0 || Nodes == 0) {
114  CmtyVV.Clr();
115  return;
116  }
117  TIntV ComSzSeq, MemSeq;
118  TAGMUtil::GenPLSeq(ComSzSeq,Coms,ComSzAlpha,Rnd,MinSz,MaxSz);
119  TAGMUtil::GenPLSeq(MemSeq,Nodes,MemAlpha,Rnd,MinK,MaxK);
120  TIntPrV CIDSzPrV, NIDMemPrV;
121  for (int i = 0; i < ComSzSeq.Len(); i++) {
122  CIDSzPrV.Add(TIntPr(i, ComSzSeq[i]));
123  }
124  for (int i = 0; i < MemSeq.Len(); i++) {
125  NIDMemPrV.Add(TIntPr(NIDV[i], MemSeq[i]));
126  }
127  TAGMUtil::ConnectCmtyVV(CmtyVV, CIDSzPrV, NIDMemPrV, Rnd);
128 }
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TAGMUtil::GenPLSeq
static void GenPLSeq(TIntV &SzSeq, const int &SeqLen, const double &Alpha, TRnd &Rnd, const int &Min, const int &Max)
AGMUtil:: Utilities for AGM.
Definition: agm.cpp:81
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TAGMUtil::ConnectCmtyVV
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 distributio...
Definition: agm.cpp:131
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

92  {
93  TIntV NIDV(Nodes, 0);
94  for (int i = 0; i < Nodes; i++) {
95  NIDV.Add(i);
96  }
97  GenCmtyVVFromPL(CmtyVV, NIDV, Nodes, Coms, ComSzAlpha, MemAlpha, MinSz, MaxSz, MinK, MaxK, Rnd);
98 }
TAGMUtil::GenCmtyVVFromPL
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 distributio...
Definition: agm.cpp:101
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.

81  {
82  SzSeq.Gen(SeqLen, 0);
83  while (SzSeq.Len() < SeqLen) {
84  int Sz = (int) TMath::Round(Rnd.GetPowerDev(Alpha));
85  if (Sz >= Min && Sz <= Max) {
86  SzSeq.Add(Sz);
87  }
88  }
89 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TMath::Round
static double Round(const double &Val)
Definition: xmath.h:16
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TRnd::GetPowerDev
double GetPowerDev(const double &AlphaSlope)
Definition: dt.h:47
double TAGMUtil::GetConductance ( const PUNGraph &  Graph,
const TIntSet &  CmtyS,
const int  Edges 
)
static

Definition at line 683 of file agm.cpp.

683  {
684  const int Edges2 = Edges >= 0 ? 2*Edges : Graph->GetEdges();
685  int Vol = 0, Cut = 0;
686  double Phi = 0.0;
687  for (int i = 0; i < CmtyS.Len(); i++) {
688  if (! Graph->IsNode(CmtyS[i])) { continue; }
689  TUNGraph::TNodeI NI = Graph->GetNI(CmtyS[i]);
690  for (int e = 0; e < NI.GetOutDeg(); e++) {
691  if (! CmtyS.IsKey(NI.GetOutNId(e))) { Cut += 1; }
692  }
693  Vol += NI.GetOutDeg();
694  }
695  // get conductance
696  if (Vol != Edges2) {
697  if (2 * Vol > Edges2) { Phi = Cut / double (Edges2 - Vol); }
698  else if (Vol == 0) { Phi = 0.0; }
699  else { Phi = Cut / double(Vol); }
700  } else {
701  if (Vol == Edges2) { Phi = 1.0; }
702  }
703  return Phi;
704 }
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
TUNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:94
THashSet::Len
int Len() const
Definition: shash.h:1121
TUNGraph::TNodeI::GetOutNId
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:106
void TAGMUtil::GetIntersection ( const THashSet< TInt > &  A,
const THashSet< TInt > &  B,
THashSet< TInt > &  C 
)
static

Definition at line 404 of file agm.cpp.

404  {
405  C.Gen(A.Len());
406  if (A.Len() < B.Len()) {
407  for (THashSetKeyI<TInt> it = A.BegI(); it < A.EndI(); it++)
408  if (B.IsKey(it.GetKey())) C.AddKey(it.GetKey());
409  } else {
410  for (THashSetKeyI<TInt> it = B.BegI(); it < B.EndI(); it++)
411  if (A.IsKey(it.GetKey())) C.AddKey(it.GetKey());
412  }
413 }
THashSet::BegI
TIter BegI() const
Definition: shash.h:1105
THashSet::Gen
void Gen(const int &ExpectVals)
Definition: shash.h:1115
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
THashSet::EndI
TIter EndI() const
Definition: shash.h:1112
THashSet::Len
int Len() const
Definition: shash.h:1121
void TAGMUtil::GetNbhCom ( const PUNGraph &  Graph,
const int  NID,
TIntSet &  NBCmtyS 
)
static

Definition at line 706 of file agm.cpp.

706  {
707  TUNGraph::TNodeI NI = Graph->GetNI(NID);
708  NBCmtyS.Gen(NI.GetDeg());
709  NBCmtyS.AddKey(NID);
710  for (int e = 0; e < NI.GetDeg(); e++) {
711  NBCmtyS.AddKey(NI.GetNbrNId(e));
712  }
713 }
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
THashSet::Gen
void Gen(const int &ExpectVals)
Definition: shash.h:1115
TUNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:90
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TUNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:111
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.

335  {
336  NIDComVH.Clr();
337  for (int i = 0; i < CmtyVV.Len(); i++){
338  int CID = i;
339  for (int j = 0; j < CmtyVV[i].Len(); j++) {
340  int NID = CmtyVV[i][j];
341  NIDComVH.AddDat(NID).AddKey(CID);
342  }
343  }
344 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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.

347  {
348  NIDComVH.Clr();
349  for (int u = 0; u < NIDV.Len(); u++) {
350  NIDComVH.AddDat(NIDV[u]);
351  }
352  for (int i = 0; i < CmtyVV.Len(); i++){
353  int CID = i;
354  for (int j = 0; j < CmtyVV[i].Len(); j++) {
355  int NID = CmtyVV[i][j];
356  NIDComVH.AddDat(NID).AddKey(CID);
357  }
358  }
359 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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.

324  {
325  NIDComVH.Clr();
326  for (THash<TInt,TIntV>::TIter HI = CmtyVH.BegI(); HI < CmtyVH.EndI(); HI++){
327  for (int j = 0;j < HI.GetDat().Len(); j++) {
328  int NID = HI.GetDat()[j];
329  NIDComVH.AddDat(NID)++;
330  }
331  }
332 }
THash::BegI
TIter BegI() const
Definition: hash.h:213
THash::EndI
TIter EndI() const
Definition: hash.h:218
THash
Definition: hash.h:97
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void TAGMUtil::GetNodeMembership ( THash< TInt, TIntSet > &  NIDComVH,
const TVec< TIntSet > &  CmtyVV 
)
static

Definition at line 362 of file agm.cpp.

362  {
363  for (int i = 0; i < CmtyVV.Len(); i++){
364  int CID = i;
365  for (TIntSet::TIter SI = CmtyVV[i].BegI(); SI < CmtyVV[i].EndI(); SI++) {
366  int NID = SI.GetKey();
367  NIDComVH.AddDat(NID).AddKey(CID);
368  }
369  }
370 }
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void TAGMUtil::GetNodeMembership ( THash< TInt, TIntSet > &  NIDComVH,
const THash< TInt, TIntV > &  CmtyVH 
)
static

Definition at line 371 of file agm.cpp.

371  {
372  for (THash<TInt,TIntV>::TIter HI = CmtyVH.BegI(); HI < CmtyVH.EndI(); HI++){
373  int CID = HI.GetKey();
374  for (int j = 0; j < HI.GetDat().Len(); j++) {
375  int NID = HI.GetDat()[j];
376  NIDComVH.AddDat(NID).AddKey(CID);
377  }
378  }
379 }
THash::BegI
TIter BegI() const
Definition: hash.h:213
THash::EndI
TIter EndI() const
Definition: hash.h:218
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
THash
Definition: hash.h:97
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void TAGMUtil::GetNodeMembership ( THash< TInt, TIntV > &  NIDComVH,
const THash< TInt, TIntV > &  CmtyVH 
)
static

Definition at line 381 of file agm.cpp.

381  {
382  for (int i = 0; i < CmtyVH.Len(); i++){
383  int CID = CmtyVH.GetKey(i);
384  for (int j = 0; j < CmtyVH[i].Len(); j++) {
385  int NID = CmtyVH[i][j];
386  NIDComVH.AddDat(NID).Add(CID);
387  }
388  }
389 }
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::Len
int Len() const
Definition: hash.h:228
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
void TAGMUtil::GetNodeMembership ( THash< TInt, TIntV > &  NIDComVH,
const TVec< TIntV > &  CmtyVV 
)
static

Definition at line 391 of file agm.cpp.

391  {
392  THash<TInt,TIntV> CmtyVH;
393  for (int i = 0; i < CmtyVV.Len(); i++) {
394  CmtyVH.AddDat(i, CmtyVV[i]);
395  }
396  GetNodeMembership(NIDComVH, CmtyVH);
397 }
TAGMUtil::GetNodeMembership
static void GetNodeMembership(THash< TInt, TIntSet > &NIDComVH, const TVec< TIntV > &CmtyVV)
get hash table of
Definition: agm.cpp:335
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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.

105  {
106  TStrV Colors = TStrV::GetV("red","blue","green","pink","cyan");
107  TStrV Shapes = TStrV::GetV("ellipse","triangle","square","pentagon","hexagon");
108  THash<TInt,TIntV> NIDComVH;
109  GetNodeMembership(NIDComVH,CmtyVV);
110 
111  const TStr Ext = OutFNm.GetFExt();
112  const TStr GraphFNm = OutFNm.GetSubStr(0, OutFNm.Len() - Ext.Len()) + "dot";
113  const bool IsDir = HasGraphFlag(typename PGraph::TObj, gfDirected);
114  FILE *F = fopen(GraphFNm.CStr(), "wt");
115  if (! Desc.Empty()) fprintf(F, "/*****\n%s\n*****/\n\n", Desc.CStr());
116  if (IsDir) { fprintf(F, "digraph G {\n"); } else { fprintf(F, "graph G {\n"); }
117  fprintf(F, " graph [splines=false overlap=false]\n"); //size=\"12,10\" ratio=fill
118  fprintf(F, " node [width=0.3, height=0.3]\n");
119  //nodes
120  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
121  int NID = NI.GetId();
122  TIntV& CIDV = NIDComVH.GetDat(NID);
123  IAssert(CIDV.Len()>0);
124  TStr ShapeNm = Shapes[(CIDV.Len()-1) % Shapes.Len()];
125  TStr ColorNm = Colors[CIDV[0] % Colors.Len()];
126  TStr NodeComLabel = TStr::Fmt("%d(",NID);
127  for(int i=0;i<CIDV.Len();i++) {
128  TStr TmpStr = TStr::Fmt("%d",int(CIDV[i]));
129  NodeComLabel += TmpStr;
130  if(i<CIDV.Len()-1){NodeComLabel+=",";}
131  }
132  NodeComLabel += ")";
133  fprintf(F, " %d [style=filled, shape=\"%s\" fillcolor=\"%s\" label=\"%s\"];\n", NI.GetId(), ShapeNm.CStr(),ColorNm.CStr(), NodeComLabel.CStr());
134  }
135 
136  // edges
137  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
138  if (NI.GetOutDeg()==0 && NI.GetInDeg()==0 ) {
139  fprintf(F, "%d;\n", NI.GetId()); }
140  else {
141  for (int e = 0; e < NI.GetOutDeg(); e++) {
142  if (! IsDir && NI.GetId() > NI.GetOutNId(e)) { continue; }
143  fprintf(F, " %d %s %d;\n", NI.GetId(), IsDir?"->":"--", NI.GetOutNId(e));
144  }
145  }
146  }
147  if (! Desc.Empty()) {
148  fprintf(F, " label = \"\\n%s\\n\";", Desc.CStr());
149  fprintf(F, " fontsize=24;\n");
150  }
151  fprintf(F, "}\n");
152  fclose(F);
153  TSnap::TSnapDetail::GVizDoLayout(GraphFNm, OutFNm, gvlNeato);
154  }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TStr::Len
int Len() const
Definition: dt.h:490
TAGMUtil::GetNodeMembership
static void GetNodeMembership(THash< TInt, TIntSet > &NIDComVH, const TVec< TIntV > &CmtyVV)
get hash table of
Definition: agm.cpp:335
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TStr::GetSubStr
TStr GetSubStr(const int &BChN, const int &EChN) const
Definition: dt.cpp:811
TStr::GetFExt
TStr GetFExt() const
Definition: dt.cpp:1421
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
gvlNeato
Definition: gviz.h:3
TSnap::TSnapDetail::GVizDoLayout
void GVizDoLayout(const TStr &GraphInFNm, TStr OutFNm, const TGVizLayout &Layout)
Runs GraphViz layout engine over a graph saved in the file GraphInFNm with output saved to OutFNm...
Definition: gviz.cpp:5
HasGraphFlag
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
gfDirected
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
TStr
Definition: dt.h:412
TStr::Empty
bool Empty() const
Definition: dt.h:491
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TVec< TStr >::GetV
static TVec< TStr, int > GetV(const TStr &Val1)
Returns a vector on element Val1.
Definition: ds.h:848
TStr::CStr
char * CStr()
Definition: dt.h:479
int TAGMUtil::Intersection ( const TIntV &  C1,
const TIntV &  C2 
)
static

Definition at line 399 of file agm.cpp.

399  {
400  TIntSet S1(C1), S2(C2);
401  return TAGMUtil::Intersection(S1, S2);
402 }
TAGMUtil::Intersection
static int Intersection(const TIntV &C1, const TIntV &C2)
Definition: agm.cpp:399
int TAGMUtil::Intersection ( const THashSet< TInt > &  A,
const THashSet< TInt > &  B 
)
static

Definition at line 415 of file agm.cpp.

415  {
416  int n = 0;
417  if (A.Len() < B.Len()) {
418  for (THashSetKeyI<TInt> it = A.BegI(); it < A.EndI(); it++)
419  if (B.IsKey(it.GetKey())) n++;
420  } else {
421  for (THashSetKeyI<TInt> it = B.BegI(); it < B.EndI(); it++)
422  if (A.IsKey(it.GetKey())) n++;
423  }
424  return n;
425 }
THashSet::BegI
TIter BegI() const
Definition: shash.h:1105
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
THashSet::EndI
TIter EndI() const
Definition: shash.h:1112
THashSet::Len
int Len() const
Definition: shash.h:1121
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.

246  {
247  CmtyVV.Gen(Kilo(100), 0);
248  TSsParser Ss(InFNm, ssfWhiteSep);
249  while (Ss.Next()) {
250  if(Ss.GetFlds() > 0) {
251  TIntV CmtyV;
252  for (int i = 0; i < Ss.GetFlds(); i++) {
253  if (Ss.IsInt(i)) {
254  CmtyV.Add(Ss.GetInt(i));
255  }
256  }
257  CmtyVV.Add(CmtyV);
258  }
259  }
260  CmtyVV.Pack();
261  printf("community loading completed (%d communities)\n",CmtyVV.Len());
262 
263 }
Kilo
#define Kilo(n)
Definition: gbase.h:3
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSsParser
Definition: ss.h:72
ssfWhiteSep
Whitespace (space or tab) separated.
Definition: ss.h:11
TVec::Pack
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

266  {
267  CmtyVV.Gen(Kilo(100), 0);
268  TSsParser Ss(InFNm, Sep);
269  while (Ss.Next()) {
270  if(Ss.GetFlds() > BeginCol) {
271  TIntV CmtyV;
272  for (int i = BeginCol; i < Ss.GetFlds(); i++) {
273  if (StrToNIdH.IsKey(Ss.GetFld(i))) {
274  CmtyV.Add(StrToNIdH.GetKeyId(Ss.GetFld(i)));
275  }
276  }
277  if (CmtyV.Len() < MinSz) { continue; }
278  CmtyVV.Add(CmtyV);
279  }
280  }
281  CmtyVV.Pack();
282  printf("community loading completed (%d communities)\n",CmtyVV.Len());
283 }
Kilo
#define Kilo(n)
Definition: gbase.h:3
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSsParser
Definition: ss.h:72
TStrHash::IsKey
bool IsKey(const char *Key) const
Definition: hash.h:897
TVec::Pack
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TStrHash::GetKeyId
int GetKeyId(const char *Key) const
Definition: hash.h:994
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.

67  {
68  TSsParser Ss(InFNm, SsFmt);
69  PGraph Graph = PGraph::TObj::New();
70  TStrHash<TInt> StrSet(Mega(1), true);
71  while (Ss.Next()) {
72  const int SrcNId = StrSet.AddKey(Ss[SrcColId]);
73  const int DstNId = StrSet.AddKey(Ss[DstColId]);
74  if (! Graph->IsNode(SrcNId)) { Graph->AddNode(SrcNId); }
75  if (! Graph->IsNode(DstNId)) { Graph->AddNode(DstNId); }
76  Graph->AddEdge(SrcNId, DstNId);
77  }
78  NIDNameH.Gen(StrSet.Len());
79  for (int s = 0; s < StrSet.Len(); s++) { NIDNameH.AddDat(s, StrSet.GetKey(s)); }
80  IAssert(NIDNameH.Len() == Graph->GetNodes());
81 
82  Graph->Defrag();
83  return Graph;
84  }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TSsParser
Definition: ss.h:72
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:222
Mega
#define Mega(n)
Definition: gbase.h:4
TStrHash
Definition: hash.h:781
THash::Len
int Len() const
Definition: hash.h:228
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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.

86  {
87  TSsParser Ss(InFNm, SsFmt);
88  PGraph Graph = PGraph::TObj::New();
89  TStrHash<TInt> StrSet(Mega(1), true);
90  while (Ss.Next()) {
91  const int SrcNId = StrSet.AddKey(Ss[SrcColId]);
92  const int DstNId = StrSet.AddKey(Ss[DstColId]);
93  if (! Graph->IsNode(SrcNId)) { Graph->AddNode(SrcNId); }
94  if (! Graph->IsNode(DstNId)) { Graph->AddNode(DstNId); }
95  Graph->AddEdge(SrcNId, DstNId);
96  }
97  NodeNameH = StrSet;
98  NodeNameH.Pack();
99 
100  Graph->Defrag();
101  return Graph;
102  }
TSsParser
Definition: ss.h:72
TStrHash::Pack
void Pack()
Definition: hash.h:915
Mega
#define Mega(n)
Definition: gbase.h:4
TStrHash
Definition: hash.h:781
void TAGMUtil::RewireCmtyNID ( THash< TInt, TIntV > &  CmtyVH,
TRnd &  Rnd 
)
static

rewire bipartite community affiliation graphs

Definition at line 202 of file agm.cpp.

202  {
203  THash<TInt,TIntV > NewCmtyVH(CmtyVH.Len());
204  TIntV NDegV;
205  TIntV CDegV;
206  for (int i = 0; i < CmtyVH.Len(); i++) {
207  int CID = CmtyVH.GetKey(i);
208  for (int j = 0; j < CmtyVH[i].Len(); j++) {
209  int NID = CmtyVH[i][j];
210  NDegV.Add(NID);
211  CDegV.Add(CID);
212  }
213  }
214  TIntPrSet CNIDSet(CDegV.Len());
215  int c=0;
216  while (c++ < 15 && CDegV.Len() > 1){
217  for (int i = 0; i < CDegV.Len(); i++) {
218  int u = Rnd.GetUniDevInt(CDegV.Len());
219  int v = Rnd.GetUniDevInt(NDegV.Len());
220  if (CNIDSet.IsKey(TIntPr(CDegV[u], NDegV[v]))) { continue; }
221  CNIDSet.AddKey(TIntPr(CDegV[u], NDegV[v]));
222  if (u == CDegV.Len() - 1) {
223  CDegV.DelLast();
224  } else {
225  CDegV[u] = CDegV.Last();
226  CDegV.DelLast();
227  }
228  if ( v == NDegV.Len() - 1) {
229  NDegV.DelLast();
230  } else{
231  NDegV[v] = NDegV.Last();
232  NDegV.DelLast();
233  }
234  }
235  }
236  for (int i = 0; i < CNIDSet.Len(); i++) {
237  TIntPr CNIDPr = CNIDSet[i];
238  IAssert(CmtyVH.IsKey(CNIDPr.Val1));
239  NewCmtyVH.AddDat(CNIDPr.Val1);
240  NewCmtyVH.GetDat(CNIDPr.Val1).Add(CNIDPr.Val2);
241  }
242  CmtyVH = NewCmtyVH;
243 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
TPair
Definition: ds.h:32
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TPair::Val2
TVal2 Val2
Definition: ds.h:35
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVec::DelLast
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
THash::Len
int Len() const
Definition: hash.h:228
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
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.

192  {
193  THash<TInt,TIntV> CmtyVH;
194  for (int i = 0; i < CmtyVVIn.Len(); i++) {
195  CmtyVH.AddDat(i, CmtyVVIn[i]);
196  }
197  TAGMUtil::RewireCmtyNID(CmtyVH, Rnd);
198  CmtyVH.GetDatV(CmtyVVOut);
199 }
THash::GetDatV
void GetDatV(TVec< TDat > &DatV) const
Definition: hash.h:492
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TAGMUtil::RewireCmtyNID
static void RewireCmtyNID(THash< TInt, TIntV > &CmtyVH, TRnd &Rnd)
rewire bipartite community affiliation graphs
Definition: agm.cpp:202
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.

486  {
488  if (CmtyVV.Len() == 0) { return; }
489  double NXMin = 0.1, YMin = 0.1, NXMax = 250.00, YMax = 30.0;
490  double CXMin = 0.3 * NXMax, CXMax = 0.7 * NXMax;
491  double CStep = (CXMax - CXMin) / (double) CmtyVV.Len(), NStep = (NXMax - NXMin) / (double) NIDV.Len();
492  THash<TInt,TIntV> NIDComVH;
493  TAGMUtil::GetNodeMembership(NIDComVH, CmtyVV);
494 
495  FILE* F = fopen(OutFNm.CStr(), "wt");
496  fprintf(F, "<?xml version='1.0' encoding='UTF-8'?>\n");
497  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");
498  fprintf(F, "\t<graph mode='static' defaultedgetype='directed'>\n");
499  fprintf(F, "\t\t<nodes>\n");
500  for (int c = 0; c < CmtyVV.Len(); c++) {
501  int CID = c;
502  double XPos = c * CStep + CXMin;
503  TIntTr Color = CIDColorH.IsKey(CID)? CIDColorH.GetDat(CID) : TIntTr(120, 120, 120);
504  fprintf(F, "\t\t\t<node id='C%d' label='C%d'>\n", CID, CID);
505  fprintf(F, "\t\t\t\t<viz:color r='%d' g='%d' b='%d'/>\n", Color.Val1.Val, Color.Val2.Val, Color.Val3.Val);
506  fprintf(F, "\t\t\t\t<viz:size value='%.3f'/>\n", MaxSz);
507  fprintf(F, "\t\t\t\t<viz:shape value='square'/>\n");
508  fprintf(F, "\t\t\t\t<viz:position x='%f' y='%f' z='0.0'/>\n", XPos, YMax);
509  fprintf(F, "\t\t\t</node>\n");
510  }
511 
512  for (int u = 0;u < NIDV.Len(); u++) {
513  int NID = NIDV[u];
514  TStr Label = NIDNameH.IsKey(NID)? NIDNameH.GetDat(NID): "";
515  double Size = MinSz;
516  double XPos = NXMin + u * NStep;
517  TIntTr Color = NIDColorH.IsKey(NID)? NIDColorH.GetDat(NID) : TIntTr(120, 120, 120);
518  double Alpha = 1.0;
519  fprintf(F, "\t\t\t<node id='%d' label='%s'>\n", NID, Label.CStr());
520  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);
521  fprintf(F, "\t\t\t\t<viz:size value='%.3f'/>\n", Size);
522  fprintf(F, "\t\t\t\t<viz:shape value='square'/>\n");
523  fprintf(F, "\t\t\t\t<viz:position x='%f' y='%f' z='0.0'/>\n", XPos, YMin);
524  fprintf(F, "\t\t\t</node>\n");
525  }
526  fprintf(F, "\t\t</nodes>\n");
527  fprintf(F, "\t\t<edges>\n");
528  int EID = 0;
529  for (int u = 0;u < NIDV.Len(); u++) {
530  int NID = NIDV[u];
531  if (NIDComVH.IsKey(NID)) {
532  for (int c = 0; c < NIDComVH.GetDat(NID).Len(); c++) {
533  int CID = NIDComVH.GetDat(NID)[c];
534  fprintf(F, "\t\t\t<edge id='%d' source='C%d' target='%d'/>\n", EID++, CID, NID);
535  }
536  }
537  }
538  fprintf(F, "\t\t</edges>\n");
539  fprintf(F, "\t</graph>\n");
540  fprintf(F, "</gexf>\n");
541 }
TAGMUtil::GetNodeMembership
static void GetNodeMembership(THash< TInt, TIntSet > &NIDComVH, const TVec< TIntV > &CmtyVV)
get hash table of
Definition: agm.cpp:335
TTriple
Definition: ds.h:130
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TTriple::Val1
TVal1 Val1
Definition: ds.h:132
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TTriple::Val2
TVal2 Val2
Definition: ds.h:133
TStr
Definition: dt.h:412
TIntTr
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:171
TStr::CStr
char * CStr()
Definition: dt.h:479
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TTriple::Val3
TVal3 Val3
Definition: ds.h:134
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.

55  {
56  THash<TInt, TStr> TmpH;
57  SaveGephi(OutFNm, G, CmtyVVAtr, MaxSz, MinSz, TmpH);
58  }
TAGMUtil::SaveGephi
static void SaveGephi(const TStr &OutFNm, const PUNGraph &G, const TVec< TIntV > &CmtyVVAtr, const double MaxSz, const double MinSz)
Definition: agm.h:55
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.

59  {
60  THash<TInt, TIntTr> TmpH;
61  SaveGephi(OutFNm, G, CmtyVVAtr, MaxSz, MinSz, NIDNameH, TmpH);
62  }
TAGMUtil::SaveGephi
static void SaveGephi(const TStr &OutFNm, const PUNGraph &G, const TVec< TIntV > &CmtyVVAtr, const double MaxSz, const double MinSz)
Definition: agm.h:55
THash
Definition: hash.h:97
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.

428  {
429  THash<TInt,TIntV> NIDComVHAtr;
430  TAGMUtil::GetNodeMembership(NIDComVHAtr, CmtyVVAtr);
431 
432  FILE* F = fopen(OutFNm.CStr(), "wt");
433  fprintf(F, "<?xml version='1.0' encoding='UTF-8'?>\n");
434  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");
435  fprintf(F, "\t<graph mode='static' defaultedgetype='undirected'>\n");
436  if (CmtyVVAtr.Len() > 0) {
437  fprintf(F, "\t<attributes class='node'>\n");
438  for (int c = 0; c < CmtyVVAtr.Len(); c++) {
439  fprintf(F, "\t\t<attribute id='%d' title='c%d' type='boolean'>", c, c);
440  fprintf(F, "\t\t<default>false</default>\n");
441  fprintf(F, "\t\t</attribute>\n");
442  }
443  fprintf(F, "\t</attributes>\n");
444  }
445  fprintf(F, "\t\t<nodes>\n");
446  for (TUNGraph::TNodeI NI = G->BegNI(); NI < G->EndNI(); NI++) {
447  int NID = NI.GetId();
448  TStr Label = NIDNameH.IsKey(NID)? NIDNameH.GetDat(NID): "";
449  TIntTr Color = NIDColorH.IsKey(NID)? NIDColorH.GetDat(NID) : TIntTr(120, 120, 120);
450 
451  double Size = MinSz;
452  double SizeStep = (MaxSz - MinSz) / (double) CmtyVVAtr.Len();
453  if (NIDComVHAtr.IsKey(NID)) {
454  Size = MinSz + SizeStep * (double) NIDComVHAtr.GetDat(NID).Len();
455  }
456  double Alpha = 1.0;
457  fprintf(F, "\t\t\t<node id='%d' label='%s'>\n", NID, Label.CStr());
458  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);
459  fprintf(F, "\t\t\t\t<viz:size value='%.3f'/>\n", Size);
460  //specify attributes
461  if (NIDComVHAtr.IsKey(NID)) {
462  fprintf(F, "\t\t\t\t<attvalues>\n");
463  for (int c = 0; c < NIDComVHAtr.GetDat(NID).Len(); c++) {
464  int CID = NIDComVHAtr.GetDat(NID)[c];
465  fprintf(F, "\t\t\t\t\t<attvalue for='%d' value='true'/>\n", CID);
466  }
467  fprintf(F, "\t\t\t\t</attvalues>\n");
468  }
469 
470  fprintf(F, "\t\t\t</node>\n");
471  }
472  fprintf(F, "\t\t</nodes>\n");
473  //plot edges
474  int EID = 0;
475  fprintf(F, "\t\t<edges>\n");
476  for (TUNGraph::TEdgeI EI = G->BegEI(); EI < G->EndEI(); EI++) {
477  fprintf(F, "\t\t\t<edge id='%d' source='%d' target='%d'/>\n", EID++, EI.GetSrcNId(), EI.GetDstNId());
478  }
479  fprintf(F, "\t\t</edges>\n");
480  fprintf(F, "\t</graph>\n");
481  fprintf(F, "</gexf>\n");
482  fclose(F);
483 }
TUNGraph::TEdgeI
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
TAGMUtil::GetNodeMembership
static void GetNodeMembership(THash< TInt, TIntSet > &NIDComVH, const TVec< TIntV > &CmtyVV)
get hash table of
Definition: agm.cpp:335
TTriple
Definition: ds.h:130
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TTriple::Val1
TVal1 Val1
Definition: ds.h:132
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TTriple::Val2
TVal2 Val2
Definition: ds.h:133
TStr
Definition: dt.h:412
TIntTr
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:171
TStr::CStr
char * CStr()
Definition: dt.h:479
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TTriple::Val3
TVal3 Val3
Definition: ds.h:134
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.

315  {
316  int M = 0;
317  for (int i = 0; i < CmtyVV.Len(); i++) {
318  M += CmtyVV[i].Len();
319  }
320  return M;
321 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
The documentation for this class was generated from the following files: