SNAP Library 2.3, Developer Reference  2014-06-16 11:58:46
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
TAGM Class Reference

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

#include <agm.h>

Static Public Member Functions

static void RndConnectInsideCommunity (PUNGraph &Graph, const TIntV &CmtyV, const double &Prob, TRnd &Rnd)
 Connect members of a given community by Erdos-Renyi. More...
 
static PUNGraph GenAGM (TVec< TIntV > &CmtyVV, const double &DensityCoef, const double &ScaleCoef, TRnd &Rnd=TInt::Rnd)
 
static PUNGraph GenAGM (TVec< TIntV > &CmtyVV, const double &DensityCoef, const int TargetEdges, TRnd &Rnd)
 
static PUNGraph GenAGM (TVec< TIntV > &CmtyVV, const TFltV &CProbV, TRnd &Rnd, const double PNoCom=-1.0)
 Generate graph using the AGM model. CProbV = vector of Pc. More...
 

Detailed Description

Affiliaiton Graph Model (AGM) graph generator.

Definition at line 7 of file agm.h.

Member Function Documentation

PUNGraph TAGM::GenAGM ( TVec< TIntV > &  CmtyVV,
const double &  DensityCoef,
const double &  ScaleCoef,
TRnd Rnd = TInt::Rnd 
)
static

Definition at line 37 of file agm.cpp.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().

Referenced by GenAGM().

37  {
38  TFltV CProbV;
39  double Prob;
40  for (int i = 0; i < CmtyVV.Len(); i++) {
41  Prob = ScaleCoef*pow( double( CmtyVV[i].Len()), - DensityCoef);
42  if (Prob > 1.0) { Prob = 1; }
43  CProbV.Add(Prob);
44  }
45  return TAGM::GenAGM(CmtyVV, CProbV, Rnd);
46 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
static PUNGraph GenAGM(TVec< TIntV > &CmtyVV, const double &DensityCoef, const double &ScaleCoef, TRnd &Rnd=TInt::Rnd)
Definition: agm.cpp:37
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420

Here is the call graph for this function:

Here is the caller graph for this function:

PUNGraph TAGM::GenAGM ( TVec< TIntV > &  CmtyVV,
const double &  DensityCoef,
const int  TargetEdges,
TRnd Rnd 
)
static

Definition at line 31 of file agm.cpp.

References GenAGM(), and TUNGraph::GetEdges().

31  {
32  PUNGraph TryG = TAGM::GenAGM(CmtyVV, DensityCoef, 1.0, Rnd);
33  const double ScaleCoef = (double) TargetEdges / (double) TryG->GetEdges();
34  return TAGM::GenAGM(CmtyVV, DensityCoef, ScaleCoef, Rnd);
35 }
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:74
static PUNGraph GenAGM(TVec< TIntV > &CmtyVV, const double &DensityCoef, const double &ScaleCoef, TRnd &Rnd=TInt::Rnd)
Definition: agm.cpp:37

Here is the call graph for this function:

PUNGraph TAGM::GenAGM ( TVec< TIntV > &  CmtyVV,
const TFltV CProbV,
TRnd Rnd,
const double  PNoCom = -1.0 
)
static

Generate graph using the AGM model. CProbV = vector of Pc.

Definition at line 49 of file agm.cpp.

References THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), TUNGraph::Defrag(), TUNGraph::GetEdges(), THashSet< TKey, THashFunc >::GetKeyV(), TUNGraph::GetNodes(), TUNGraph::IsNode(), TVec< TVal, TSizeTy >::Len(), TUNGraph::New(), and RndConnectInsideCommunity().

49  {
50  PUNGraph G = TUNGraph::New(100 * CmtyVV.Len(), -1);
51  printf("AGM begins\n");
52  for (int i = 0; i < CmtyVV.Len(); i++) {
53  TIntV& CmtyV = CmtyVV[i];
54  for (int u = 0; u < CmtyV.Len(); u++) {
55  if ( G->IsNode(CmtyV[u])) { continue; }
56  G->AddNode(CmtyV[u]);
57  }
58  double Prob = CProbV[i];
59  RndConnectInsideCommunity(G, CmtyV, Prob, Rnd);
60  }
61  if (PNoCom > 0.0) { //if we want to connect nodes that do not share any community
62  TIntSet NIDS;
63  for (int c = 0; c < CmtyVV.Len(); c++) {
64  for (int u = 0; u < CmtyVV[c].Len(); u++) {
65  NIDS.AddKey(CmtyVV[c][u]);
66  }
67  }
68  TIntV NIDV;
69  NIDS.GetKeyV(NIDV);
70  RndConnectInsideCommunity(G,NIDV,PNoCom,Rnd);
71  }
72  printf("AGM completed (%d nodes %d edges)\n",G->GetNodes(),G->GetEdges());
73  G->Defrag();
74  return G;
75 }
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:74
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
void GetKeyV(TVec< TKey > &KeyV) const
Definition: shash.h:1341
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:162
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:149
int AddKey(const TKey &Key)
Definition: shash.h:1248
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:132
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:199
static void RndConnectInsideCommunity(PUNGraph &Graph, const TIntV &CmtyV, const double &Prob, TRnd &Rnd)
Connect members of a given community by Erdos-Renyi.
Definition: agm.cpp:10

Here is the call graph for this function:

void TAGM::RndConnectInsideCommunity ( PUNGraph Graph,
const TIntV CmtyV,
const double &  Prob,
TRnd Rnd 
)
static

Connect members of a given community by Erdos-Renyi.

Definition at line 10 of file agm.cpp.

References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TRnd::GetBinomialDev(), TRnd::GetUniDevInt(), THashSet< TKey, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), and Swap().

Referenced by GenAGM().

10  {
11  int CNodes = CmtyV.Len(), CEdges;
12  if (CNodes < 20) {
13  CEdges = (int) Rnd.GetBinomialDev(Prob, CNodes * (CNodes-1) / 2);
14  } else {
15  CEdges = (int) (Prob * CNodes * (CNodes - 1) / 2);
16  }
17  THashSet<TIntPr> NewEdgeSet(CEdges);
18  for (int edge = 0; edge < CEdges; ) {
19  int SrcNId = CmtyV[Rnd.GetUniDevInt(CNodes)];
20  int DstNId = CmtyV[Rnd.GetUniDevInt(CNodes)];
21  if (SrcNId > DstNId) { Swap(SrcNId,DstNId); }
22  if (SrcNId != DstNId && ! NewEdgeSet.IsKey(TIntPr(SrcNId, DstNId))) { // is new edge
23  NewEdgeSet.AddKey(TIntPr(SrcNId, DstNId));
24  Graph->AddEdge(SrcNId, DstNId);
25  edge++;
26  }
27  }
28 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:84
Definition: ds.h:32
double GetBinomialDev(const double &Prb, const int &Trials)
Definition: dt.cpp:154
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
void Swap(TRec &Rec1, TRec &Rec2)
Definition: bd.h:568

Here is the call graph for this function:

Here is the caller graph for this function:


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