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

#include <timenet.h>

Inherits TNodeNet< TSecTm >.

Classes

class  TTmBucket
 

Public Types

typedef TNodeNet< TSecTmTNet
 
typedef TPt< TNodeNet< TSecTm > > PNet
 
typedef TVec< TTmBucketTTmBucketV
 
- Public Types inherited from TNodeNet< TSecTm >
typedef TSecTm TNodeDat
 
typedef TNodeNet< TSecTmTNet
 
typedef TPt< TNetPNet
 

Public Member Functions

 TTimeNet ()
 
 TTimeNet (const int &Nodes, const int &Edges)
 
 TTimeNet (const TTimeNet &TimeNet)
 
 TTimeNet (TSIn &SIn)
 
void Save (TSOut &SOut) const
 Saves the network to a (binary) stream SOut. More...
 
TTimeNetoperator= (const TTimeNet &TimeNet)
 
PTimeNet GetSubGraph (const TIntV &NIdV) const
 
PTimeNENet GetTimeNENet () const
 
void GetNIdByTm (TIntV &NIdV) const
 
void GetTmBuckets (const TTmUnit &GroupBy, TTmBucketV &TmBucketV) const
 
void GetNodeBuckets (const int NodesPerBucket, TTimeNet::TTmBucketV &TmBucketV) const
 
PGStatVec TimeGrowth (const TTmUnit &TmUnit, const TFSet &TakeStat, const TSecTm &StartTm) const
 
void PlotEffDiam (const TStr &FNmPref, const TStr &Desc, const TTmUnit &GroupBy, const TSecTm &StartTm, const int &NDiamRuns=10, const bool &OnlyWcc=false, const bool &AlsoRewire=false) const
 
void PlotMissingPast (const TStr &FNmPref, const TStr &Desc, const TTmUnit &GroupBy, const TSecTm &DelPreTmEdges, const TSecTm &PostTmDiam) const
 
void PlotCCfOverTm (const TStr &FNmPref, TStr Desc, const TTmUnit &TmUnit, const int &NodesBucket=-1) const
 
void PlotMedianDegOverTm (const TStr &FNmPref, const TTmUnit &TmUnit, const int &NodesPerBucket=-1) const
 
- Public Member Functions inherited from TNodeNet< TSecTm >
const TNode & GetNode (const int &NId) const
 Returns node element for the node of ID NId in the network. More...
 
 TNodeNet ()
 
 TNodeNet (const int &Nodes, const int &Edges)
 Constructor that reserves enough memory for a network of Nodes nodes and Edges edges. More...
 
 TNodeNet (const TNodeNet &NodeNet)
 
 TNodeNet (TSIn &SIn)
 Constructor that loads the network from a (binary) stream SIn. More...
 
virtual ~TNodeNet ()
 
bool HasFlag (const TGraphFlag &Flag) const
 Allows for run-time checking the type of the network (see the TGraphFlag for flags). More...
 
TNodeNetoperator= (const TNodeNet &NodeNet)
 
int GetNodes () const
 Returns the number of nodes in the network. More...
 
int AddNode (int NId=-1)
 Adds a node of ID NId to the network. More...
 
int AddNode (int NId, const TSecTm &NodeDat)
 Adds a node of ID NId and node data NodeDat to the network. More...
 
int AddNode (const TNodeI &NodeI)
 Adds a node NodeI and its node data to the network. More...
 
int AddNodeUnchecked (int NId=-1)
 Adds a node of ID NId to the network, noop if the node already exists. More...
 
virtual void DelNode (const int &NId)
 Deletes node of ID NId from the network. More...
 
void DelNode (const TNode &NodeI)
 Deletes node of ID NodeI.GetId() from the network. More...
 
bool IsNode (const int &NId) const
 Tests whether ID NId is a node. More...
 
TNodeI BegNI () const
 Returns an iterator referring to the first node in the network. More...
 
TNodeI EndNI () const
 Returns an iterator referring to the past-the-end node in the network. More...
 
TNodeI GetNI (const int &NId) const
 Returns an iterator referring to the node of ID NId in the network. More...
 
void SetNDat (const int &NId, const TSecTm &NodeDat)
 Sets node data for the node of ID NId in the network. More...
 
TSecTmGetNDat (const int &NId)
 Returns node data for the node of ID NId in the network. More...
 
const TSecTmGetNDat (const int &NId) const
 Returns node data for the node of ID NId in the network. More...
 
int GetMxNId () const
 Returns an ID that is larger than any node ID in the network. More...
 
int GetEdges () const
 Returns the number of edges in the network. More...
 
int AddEdge (const int &SrcNId, const int &DstNId)
 Adds an edge from node SrcNId to node DstNId to the network. More...
 
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the network. More...
 
void DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true)
 Deletes an edge from node IDs SrcNId to DstNId from the network. More...
 
bool IsEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
 Tests whether an edge from node IDs SrcNId to DstNId exists in the network. More...
 
TEdgeI BegEI () const
 Returns an iterator referring to the first edge in the network. More...
 
TEdgeI EndEI () const
 Returns an iterator referring to the past-the-end edge in the network. More...
 
TEdgeI GetEI (const int &EId) const
 Not supported/implemented! More...
 
TEdgeI GetEI (const int &SrcNId, const int &DstNId) const
 Returns an iterator referring to edge (SrcNId, DstNId) in the network. More...
 
int GetRndNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random node in the network. More...
 
TNodeI GetRndNI (TRnd &Rnd=TInt::Rnd)
 Returns an interator referring to a random node in the network. More...
 
void GetNIdV (TIntV &NIdV) const
 Gets a vector IDs of all nodes in the network. More...
 
bool Empty () const
 Tests whether the network is empty (has zero nodes). More...
 
void Clr (const bool &DoDel=true, const bool &ResetDat=true)
 Deletes all nodes and edges from the network. More...
 
void Reserve (const int &Nodes, const int &Edges)
 Reserves memory for a network of Nodes nodes and Edges edges. More...
 
void SortNIdById (const bool &Asc=true)
 Sorts nodes by node IDs. More...
 
void SortNIdByDat (const bool &Asc=true)
 Sorts nodes by node data. More...
 
void Defrag (const bool &OnlyNodeLinks=false)
 Defragments the network. More...
 
bool IsOk (const bool &ThrowExcept=true) const
 Checks the network data structure for internal consistency. More...
 

Static Public Member Functions

static PTimeNet New ()
 
static PTimeNet New (const int &Nodes, const int &Edges)
 
static PTimeNet Load (TSIn &SIn)
 
static PTimeNet LoadBipartite (const TStr &InFNm)
 
static PTimeNet LoadArxiv (const TStr &PaperFNm, const TStr &CiteFNm)
 
static PTimeNet LoadPatents (const TStr &PatentFNm, const TStr &CiteFNm)
 
static PTimeNet LoadAmazon (const TStr &StlFNm)
 
- Static Public Member Functions inherited from TNodeNet< TSecTm >
static PNet New ()
 Static constructor that returns a pointer to the network. Call: TPt <TNodeNet<TNodeData> > Net = TNodeNet<TNodeData>::New(). More...
 
static PNet Load (TSIn &SIn)
 Static constructor that loads the network from a stream SIn and returns a pointer to it. More...
 
static PNet LoadShM (TShMIn &ShMIn)
 Static constructor that loads the network from shared memory. More...
 

Friends

class TPt< TTimeNet >
 

Additional Inherited Members

- Protected Member Functions inherited from TNodeNet< TSecTm >
TNode & GetNode (const int &NId)
 
- Protected Attributes inherited from TNodeNet< TSecTm >
TCRef CRef
 
TInt MxNId
 
THash< TInt, TNode > NodeH
 

Detailed Description

Definition at line 16 of file timenet.h.

Member Typedef Documentation

Definition at line 19 of file timenet.h.

Definition at line 18 of file timenet.h.

Definition at line 32 of file timenet.h.

Constructor & Destructor Documentation

TTimeNet::TTimeNet ( )
inline

Definition at line 34 of file timenet.h.

34 { }
TTimeNet::TTimeNet ( const int &  Nodes,
const int &  Edges 
)
inline

Definition at line 35 of file timenet.h.

35 : TNet(Nodes, Edges) { }
TNodeNet< TSecTm > TNet
Definition: timenet.h:18
TTimeNet::TTimeNet ( const TTimeNet TimeNet)
inline

Definition at line 36 of file timenet.h.

36 : TNet(TimeNet) { }
TNodeNet< TSecTm > TNet
Definition: timenet.h:18
TTimeNet::TTimeNet ( TSIn SIn)
inline

Definition at line 37 of file timenet.h.

37 : TNet(SIn) { }
TNodeNet< TSecTm > TNet
Definition: timenet.h:18

Member Function Documentation

void TTimeNet::GetNIdByTm ( TIntV NIdV) const

Definition at line 48 of file timenet.cpp.

48  {
49  TVec<TKeyDat<TSecTm, TInt> > TmToNIdV(GetNodes(), 0);
50  for (TNodeI NodeI = BegNI(); NodeI < EndNI(); NodeI++) {
51  TmToNIdV.Add(TKeyDat<TSecTm, TInt>(NodeI.GetDat(), NodeI.GetId())); }
52  TmToNIdV.Sort();
53  NIdV.Gen(GetNodes(), 0);
54  for (int i = 0; i < TmToNIdV.Len(); i++) {
55  NIdV.Add(TmToNIdV[i].Dat); }
56 }
Definition: ds.h:346
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:221
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:189
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:219
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
void TTimeNet::GetNodeBuckets ( const int  NodesPerBucket,
TTimeNet::TTmBucketV TmBucketV 
) const

Definition at line 77 of file timenet.cpp.

77  {
78  TIntV NIdV;
79  GetNIdByTm(NIdV);
80  TmBucketV.Gen(NIdV.Len() / NodesPerBucket + 1, 0);
81  for (int i = 0; i < NIdV.Len(); i++) {
82  const int b = i/NodesPerBucket;
83  if (TmBucketV.Len() <= b) { TmBucketV.Add(TTimeNet::TTmBucket(TSecTm(b))); }
84  TmBucketV[b].NIdV.Add(NIdV[i]);
85  }
86 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Definition: tm.h:81
void GetNIdByTm(TIntV &NIdV) const
Definition: timenet.cpp:48
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
PTimeNet TTimeNet::GetSubGraph ( const TIntV NIdV) const

Definition at line 10 of file timenet.cpp.

10  {
11  PTimeNet NewNetPt = TTimeNet::New();
12  TTimeNet& NewNet = *NewNetPt;
13  NewNet.Reserve(NIdV.Len(), -1);
14  int node, edge;
15  TNodeI NI;
16  for (node = 0; node < NIdV.Len(); node++) {
17  NewNet.AddNode(NIdV[node], GetNDat(NIdV[node])); // also copy the node data
18  }
19  for (node = 0; node < NIdV.Len(); node++) {
20  NI = GetNI(NIdV[node]);
21  const int SrcNId = NI.GetId();
22  for (edge = 0; edge < NI.GetOutDeg(); edge++) {
23  const int OutNId = NI.GetOutNId(edge);
24  if (NewNet.IsNode(OutNId)) {
25  NewNet.AddEdge(SrcNId, OutNId); }
26  }
27  }
28  NewNet.Defrag();
29  return NewNetPt;
30 }
static PTimeNet New()
Definition: timenet.h:39
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSecTm & GetNDat(const int &NId)
Returns node data for the node of ID NId in the network.
Definition: network.h:229
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:217
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:223
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the network.
Definition: network.h:381
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:311
Definition: bd.h:196
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the network.
Definition: network.h:423
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a network of Nodes nodes and Edges edges.
Definition: network.h:278
PTimeNENet TTimeNet::GetTimeNENet ( ) const

Definition at line 32 of file timenet.cpp.

32  {
33  TIntV NIdV; GetNIdByTm(NIdV);
35  for (int i = 0; i < NIdV.Len(); i++) {
36  const int Src = NIdV[i];
37  const TTimeNet::TNodeI NI = GetNI(Src);
38  const TSecTm SrcTm = NI.GetDat();
39  if (! OutNet->IsNode(Src)) { OutNet->AddNode(Src, SrcTm); }
40  for (int e = 0; e < NI.GetOutDeg(); e++) {
41  if (! OutNet->IsNode(NI.GetOutNId(e))) { OutNet->AddNode(NI.GetOutNId(e), SrcTm); }
42  OutNet->AddEdge(Src, NI.GetOutNId(e), -1, SrcTm);
43  }
44  }
45  return OutNet;
46 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int GetEdges() const
Returns the number of edges in the network.
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:189
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:223
static PTimeNENet New()
Definition: timenet.h:86
Definition: tm.h:81
void GetNIdByTm(TIntV &NIdV) const
Definition: timenet.cpp:48
Definition: bd.h:196
void TTimeNet::GetTmBuckets ( const TTmUnit GroupBy,
TTmBucketV TmBucketV 
) const

Definition at line 59 of file timenet.cpp.

59  {
60  THash<TInt, TIntV> TmIdToNIdVH;
61  for (TNodeI NodeI = BegNI(); NodeI < EndNI(); NodeI++) {
62  const int TmId = NodeI().Round(TmUnit);
63  if (! TmIdToNIdVH.IsKey(TmId)) TmIdToNIdVH.AddKey(TmId);
64  TmIdToNIdVH.GetDat(TmId).Add(NodeI.GetId());
65  }
66  TVec<TPair<TInt, TIntV> > TmIdNIdVV;
67  TmIdToNIdVH.GetKeyDatPrV(TmIdNIdVV);
68  TmIdNIdVV.Sort();
69  TmBucketV.Gen(TmIdNIdVV.Len());
70  for (int i = 0; i < TmIdNIdVV.Len(); i++) {
71  TTmBucket& Bucket = TmBucketV[i];
72  Bucket.BegTm = TmIdNIdVV[i].Val1;
73  Bucket.NIdV = TmIdNIdVV[i].Val2;
74  }
75 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:221
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:219
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
int AddKey(const TKey &Key)
Definition: hash.h:373
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
static PTimeNet TTimeNet::Load ( TSIn SIn)
inlinestatic

Definition at line 41 of file timenet.h.

41 { return new TTimeNet(SIn); }
TTimeNet()
Definition: timenet.h:34
PTimeNet TTimeNet::LoadAmazon ( const TStr StlFNm)
static

Definition at line 563 of file timenet.cpp.

563  {
564  PTimeNet TimeNetPt = TTimeNet::New();
565  TTimeNet& TimeNet = *TimeNetPt;
566  TimeNet.Reserve(3953993, -1);
567  printf("Amazon Share-the-Love...\n");
568  char line [2024], MonthStr[4];
569  int NLines=0;
570  TStrV ColV;
571  FILE *F = fopen(StlFNm.CStr(), "rt");
572  while (! feof(F)) {
573  memset(line, 0, 2024);
574  fgets(line, 2024, F);
575  if (strlen(line) == 0) break;
576  TStr(line).SplitOnAllCh(',', ColV);
577  const int SrcNId = ColV[0].GetInt();
578  const int DstNId = ColV[1].GetInt();
579  // time data
580  TStr TmStr = ColV[2]; // time-format: 29JAN02:21:55:23
581  int Year = TmStr.GetSubStr(5, 6).GetInt();
582  if (Year < 10) { Year += 2000; } else { Year += 1900; }
583  MonthStr[0]=toupper(TmStr[2]); MonthStr[1]=tolower(TmStr[3]);
584  MonthStr[2]=tolower(TmStr[4]); MonthStr[3]=0;
585  const int Month = TTmInfo::GetMonthN(MonthStr, lUs);
586  const int Day = TmStr.GetSubStr(0, 1).GetInt();
587  const int Hour = TmStr.GetSubStr(8, 9).GetInt();
588  const int Min = TmStr.GetSubStr(11, 12).GetInt();
589  const int Sec = TmStr.GetSubStr(14, 15).GetInt();
590  // add nodes and links
591  if (! TimeNet.IsNode(SrcNId)) { TimeNet.AddNode(SrcNId, TSecTm(Year, Month, Day, Hour, Min, Sec)); }
592  if (! TimeNet.IsNode(DstNId)) { TimeNet.AddNode(DstNId, TSecTm(Year, Month, Day, Hour, Min, Sec)); }
593  if (! TimeNet.IsEdge(SrcNId, DstNId)) { TimeNet.AddEdge(SrcNId, DstNId); }
594  if (++NLines % 100000 == 0) printf("\r %dk", NLines/1000);
595  }
596  fclose(F);
597  printf("\r %d lines read\n", NLines);
598  printf("Graph: nodes: %d edges: %d\n", TimeNet.GetNodes(), TimeNet.GetEdges());
599  TimeNet.Defrag(true);
600  return TimeNetPt;
601 }
int GetInt() const
Definition: dt.h:581
static PTimeNet New()
Definition: timenet.h:39
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:373
TStr GetSubStr(const int &BChN, const int &EChN) const
Definition: dt.cpp:811
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:189
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:217
Definition: bd.h:63
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the network.
Definition: network.h:381
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
Definition: network.h:401
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:311
Definition: tm.h:81
Definition: dt.h:412
void SplitOnAllCh(const char &SplitCh, TStrV &StrV, const bool &SkipEmpty=true) const
Definition: dt.cpp:926
static int GetMonthN(const TStr &MonthNm, const TLoc &Loc=lUs)
Definition: tm.cpp:39
Definition: bd.h:196
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the network.
Definition: network.h:423
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a network of Nodes nodes and Edges edges.
Definition: network.h:278
char * CStr()
Definition: dt.h:479
PTimeNet TTimeNet::LoadArxiv ( const TStr PaperFNm,
const TStr CiteFNm 
)
static

Definition at line 383 of file timenet.cpp.

383  {
384  TExeTm ExeTm;
385  PTimeNet TimeNetPt = TTimeNet::New();
386  TTimeNet& TimeNet = *TimeNetPt;
387  printf("Arxiv citation graph (paper publication year)...\n");
388  // load time data (file hep-ph-slacdates)
389  char Line [1024];
390  FILE *PprF = fopen(PaperFNm.CStr(), "rt");
391  TStr StrId, StrTime;
392  TStrV StrV, StrTimeV;
393  int N = 0, DuplicateNode = 0;
394  while (! feof(PprF)) {
395  Line[0] = 0;
396  fgets(Line, 1024, PprF);
397  if (strlen(Line) == 0 || Line[0] == '#') continue;
398  Line[strlen(Line)-1] = 0; // delete trailing '\n'
399  TStr(Line).SplitOnWs(StrV); IAssert(StrV.Len() == 2);
400  StrId = StrV[0]; StrTime = StrV[1]; IAssert(!StrId.Empty() && !StrTime.Empty());
401  StrTime.SplitOnAllCh('-', StrTimeV); IAssert(StrTimeV.Len() == 3);
402  const int NodeId = StrId.GetInt();
403  if (! TimeNet.IsNode(NodeId)) {
404  const int Year = StrTimeV[0].GetInt();
405  const int Month = StrTimeV[1].GetInt();
406  const int Day = StrTimeV[2].GetInt();
407  TimeNet.AddNode(NodeId, TSecTm(Year, Month, Day));
408  } else { DuplicateNode++; }
409  if (++N % 10000 == 0) printf("\r %dk", N/1000);
410  }
411  printf("\r %d nodes read. %d duplicate nodes. %s\n", N, DuplicateNode, ExeTm.GetTmStr());
412  fclose(PprF);
413  // load citations (file hep-ph-citations)
414  int NewSrcIds=0, NewDstIds=0, DupLinks=0, NewCits=0;
415  FILE *CiteF = fopen(CiteFNm.CStr(), "rt");
416  N = 0; ExeTm.Tick();
417  printf("Loading Arxiv citations...\n");
418  TIntPrV EdgeV;
419  THash<TInt, TSecTm> NIdToTimeH;
420  while (! feof(CiteF)) {
421  Line[0] = 0;
422  fgets(Line, 1024, CiteF);
423  if (strlen(Line) == 0 || Line[0] == '#') continue;
424  Line[strlen(Line)-1] = 0; // delete trailing '\n'
425  TStr(Line).SplitOnWs(StrV); IAssert(StrV.Len() == 2);
426  const int SrcNId = StrV[0].GetInt();
427  const int DstNId = StrV[1].GetInt();
428  EdgeV.Add(TIntPr(SrcNId, DstNId));
429  // infer time of destination node -- earliest paper that cites the node (paper)
430  if (! TimeNet.IsNode(DstNId) && TimeNet.IsNode(SrcNId)) {
431  const TSecTm& SrcTm = TimeNet.GetNDat(SrcNId);
432  if (! NIdToTimeH.IsKey(DstNId)) {
433  NIdToTimeH.AddDat(DstNId, SrcTm);
434  NewDstIds++;
435  }
436  else if (NIdToTimeH.GetDat(DstNId) < SrcTm) {
437  NIdToTimeH.GetDat(DstNId) = SrcTm; }
438  }
439  if (++N % 10000 == 0) printf("\r %dk", N/1000);
440  }
441  fclose(CiteF);
442  // add infeered time nodes (nodes which are cited by papers with known time)
443  for (int i = 0; i < NIdToTimeH.Len(); i++) {
444  TimeNet.AddNode(NIdToTimeH.GetKey(i), NIdToTimeH[i]);
445  }
446  // add links
447  for (int i = 0; i < EdgeV.Len(); i++) {
448  const int SrcNId = EdgeV[i].Val1;
449  const int DstNId = EdgeV[i].Val2;
450  if (TimeNet.IsNode(SrcNId) && TimeNet.IsNode(DstNId)) {
451  if (! TimeNet.IsEdge(SrcNId, DstNId)) { TimeNet.AddEdge(SrcNId, DstNId); }
452  else { DupLinks++; }
453  } else {
454  if (! TimeNet.IsNode(SrcNId)) {
455  NewSrcIds++;
456  if (! TimeNet.IsNode(DstNId)) { NewCits++; }
457  }
458  }
459  }
460  printf("\r %d citations read. %s\n", N, ExeTm.GetTmStr());
461  printf("Graph: nodes: %d edges: %d\n", TimeNet.GetNodes(), TimeNet.GetEdges());
462  printf("Removing 0-degree nodes: %d nodes\n", TSnap::CntDegNodes(TimeNetPt, 0));
463  TIntV RmNIdV;
464  for (TTimeNet::TNodeI ni = TimeNet.BegNI(); ni < TimeNet.EndNI(); ni++) {
465  if (ni.GetDeg() == 0) { RmNIdV.Add(ni.GetId()); }
466  }
467  for (int i = 0; i < RmNIdV.Len(); i++) {
468  TimeNet.DelNode(RmNIdV[i]);
469  }
470  TimeNet.Defrag(true);
471  printf("\nFinal graph: nodes: %d edges: %d\n", TimeNet.GetNodes(), TimeNet.GetEdges());
472  printf(" Duplicate citations : %d\n", DupLinks);
473  printf(" Nodes without time which are cited : %d (add them to graph, use time of the earliest source node)\n", NewDstIds);
474  printf(" Citations between unknown time nodes : %d\n", NewCits);
475  printf(" Nodes without time which make citations: %d (do not add them into the graph)\n", NewSrcIds);
476  return TimeNetPt;
477 }
#define IAssert(Cond)
Definition: bd.h:262
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Definition: tm.h:355
static PTimeNet New()
Definition: timenet.h:39
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:221
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:373
TNodeData & GetNDat(const int &NId)
Returns node data for the node of ID NId in the network.
Definition: network.h:229
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:189
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:219
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:217
const char * GetTmStr() const
Definition: tm.h:370
virtual void DelNode(const int &NId)
Deletes node of ID NId from the network.
Definition: network.h:347
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the network.
Definition: network.h:381
void Tick()
Definition: tm.h:364
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
Definition: network.h:401
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:311
Definition: tm.h:81
Definition: dt.h:412
Definition: hash.h:97
Definition: bd.h:196
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the network.
Definition: network.h:423
void SplitOnWs(TStrV &StrV) const
Definition: dt.cpp:972
char * CStr()
Definition: dt.h:479
int CntDegNodes(const PGraph &Graph, const int &NodeDeg)
Returns the number of nodes with degree NodeDeg.
Definition: alg.h:105
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
PTimeNet TTimeNet::LoadBipartite ( const TStr InFNm)
static

Definition at line 346 of file timenet.cpp.

346  {
347  PTimeNet TimeNetPt = TTimeNet::New();
348  TTimeNet& TimeNet = *TimeNetPt;
349  PSs Ss = TSs::LoadTxt(ssfTabSep, InFNm.CStr());
350  TIntH Set1IdH; // paper ids
351  TStrV StrTimeV;
352  for (int y = 0; y < Ss->GetYLen(); y++) {
353  if (Ss->At(0, y)[0] == '#') continue; // skip comments
354  if (Ss->GetXLen(y) < 3) continue; // there must be at least one author
355  const int& SrcId = Ss->At(0, y).GetInt();
356  IAssert(! Set1IdH.IsKey(SrcId));
357  IAssert(! TimeNet.IsNode(SrcId));
358  Set1IdH.AddKey(SrcId);
359  Ss->At(1, y).SplitOnAllCh('-', StrTimeV);
360  const int Year = StrTimeV[0].GetInt();
361  const int Month = StrTimeV[1].GetInt();
362  const int Day = StrTimeV[2].GetInt();
363  const TSecTm NodeTm(Year, Month, Day);
364  TimeNet.AddNode(SrcId, NodeTm);
365  for (int dst = 2; dst < Ss->GetXLen(y); dst++) {
366  const int DstId = Ss->At(dst, y).GetInt();
367  IAssert(! Set1IdH.IsKey(DstId));
368  if (! TimeNet.IsNode(DstId)) { TimeNet.AddNode(DstId, NodeTm); }
369  else { TimeNet.GetNDat(DstId) = TMath::Mn(NodeTm, TimeNet.GetNDat(DstId)); }
370  if (! TimeNet.IsEdge(SrcId, DstId)) { TimeNet.AddEdge(SrcId, DstId); }
371  }
372  }
373  TimeNet.Defrag();
374  printf("Bipartate graph: nodes: %d edges: %d\n", TimeNet.GetNodes(), TimeNet.GetEdges());
375  printf(" Bipartate sets: %d nodes --> %d nodes\n", TSnap::CntInDegNodes(TimeNetPt, 0),
376  TSnap::CntOutDegNodes(TimeNetPt, 0));
377  return TimeNetPt;
378 }
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
static PSs LoadTxt(const TSsFmt &SsFmt, const TStr &FNm, const PNotify &Notify=NULL, const bool &IsExcelEoln=true, const int &MxY=-1, const TIntV &AllowedColNV=TIntV(), const bool &IsQStr=true)
Definition: ss.cpp:100
static PTimeNet New()
Definition: timenet.h:39
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:373
TNodeData & GetNDat(const int &NId)
Returns node data for the node of ID NId in the network.
Definition: network.h:229
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:189
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:217
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the network.
Definition: network.h:381
Tab separated.
Definition: ss.h:6
int CntInDegNodes(const PGraph &Graph, const int &NodeInDeg)
Returns the number of nodes with in-degree NodeInDeg.
Definition: alg.h:87
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
Definition: network.h:401
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:311
Definition: tm.h:81
Definition: bd.h:196
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the network.
Definition: network.h:423
char * CStr()
Definition: dt.h:479
int CntOutDegNodes(const PGraph &Graph, const int &NodeOutDeg)
Returns the number of nodes with out-degree NodeOutDeg.
Definition: alg.h:96
PTimeNet TTimeNet::LoadPatents ( const TStr PatentFNm,
const TStr CiteFNm 
)
static

Definition at line 480 of file timenet.cpp.

480  {
481  int N = 0;
482  TExeTm ExeTm;
483  PTimeNet TimeNetPt = TTimeNet::New();
484  TTimeNet& TimeNet = *TimeNetPt;
485  TimeNet.Reserve(4000000, 160000000);
486  printf("parsing patent data (patent grant year)...\n");
487  // load time data (file pat63_99.txt)
488  const int& PatIdCol = 0;
489  const int& GYearCol = 1;
490  TStrV ColV;
491  char Line [1024];
492  FILE *PatF = fopen(PatentFNm.CStr(), "rt");
493  fgets(Line, 1024, PatF); // skip 1st line
494  while (! feof(PatF)) {
495  Line[0] = 0;
496  fgets(Line, 1024, PatF);
497  if (strlen(Line) == 0) break;
498  TStr(Line).SplitOnAllCh(',', ColV, false);
499  IAssert(ColV.Len() == 23);
500  const int PatentId = ColV[PatIdCol].GetInt();
501  const int GrantYear = ColV[GYearCol].GetInt();
502  IAssert(! TimeNet.IsNode(PatentId));
503  TimeNet.AddNode(PatentId, TSecTm(GrantYear)); // pretend year is a second
504  if (++N % 100000 == 0) printf("\r %dk", N/1000);
505  }
506  printf("\r %d patents read. %s\n", N, ExeTm.GetTmStr());
507  fclose(PatF);
508  // load citations (file cite75_99.txt)
509  printf("\nLoading patent citations...\n");
510  int NewSrcIds=0, NewDstIds=0, DupLinks=0, NewCits=0;
511  N = 0; ExeTm.Tick();
512  TStr SrcId, DstId;
513  FILE *CiteF = fopen(CiteFNm.CStr(), "rt");
514  fgets(Line, 1024, CiteF); // skip 1st line
515  while (! feof(CiteF)) {
516  Line[0] = 0;
517  fgets(Line, 1024, CiteF);
518  if (strlen(Line) == 0) break;
519  Line[strlen(Line)-1] = 0; // delete trailing '\n'
520  TStr(Line).SplitOnCh(SrcId, ',', DstId);
521  const int SrcNId = SrcId.GetInt();
522  const int DstNId = DstId.GetInt();
523  if (! TimeNet.IsNode(SrcNId) && ! TimeNet.IsNode(DstNId)) {
524  //TimeNet.AddNode(SrcNId, TSecTm(1, 1, 1)); NewSrcIds++;
525  //TimeNet.AddNode(DstNId, TSecTm(1, 1, 1)); NewDstIds++;
526  NewCits++;
527  continue;
528  }
529  else if (TimeNet.IsNode(SrcNId) && ! TimeNet.IsNode(DstNId)) {
530  TimeNet.AddNode(DstNId, TimeNet.GetNDat(SrcNId)); NewDstIds++;
531  }
532  else if (! TimeNet.IsNode(SrcNId) && TimeNet.IsNode(DstNId)) {
533  TimeNet.AddNode(SrcNId, TimeNet.GetNDat(DstNId)); NewSrcIds++;
534  }
535  if (! TimeNet.IsEdge(SrcNId, DstNId)) {
536  TimeNet.AddEdge(SrcNId, DstNId);
537  } else { DupLinks++; }
538  if (++N % 100000 == 0) printf("\r %dk", N/1000);
539  }
540  fclose(CiteF);
541  printf("\r %d citations read. %s\n\n", N, ExeTm.GetTmStr());
542  printf("Graph: nodes: %d edges: %d\n", TimeNet.GetNodes(), TimeNet.GetEdges());
543  printf("Removing 0-degree nodes: %d nodes\n", TSnap::CntDegNodes(TimeNetPt, 0));
544  TIntV RmNIdV;
545  for (TTimeNet::TNodeI ni = TimeNet.BegNI(); ni < TimeNet.EndNI(); ni++) {
546  if (ni.GetDeg() == 0) { RmNIdV.Add(ni.GetId()); }
547  }
548  for (int i = 0; i < RmNIdV.Len(); i++) {
549  TimeNet.DelNode(RmNIdV[i]);
550  }
551  TimeNet.Defrag(true);
552  printf("\nFinal graph: nodes: %d edges: %d\n", TimeNet.GetNodes(), TimeNet.GetEdges());
553  printf(" Duplicate citations : %d\n", DupLinks);
554  printf(" Citations between unknown time nodes : %d\n", NewCits);
555  printf(" Nodes without time which make citations: %d\n", NewSrcIds);
556  printf(" Nodes without time which are cited : %d\n", NewDstIds);
557  return TimeNetPt;
558 }
#define IAssert(Cond)
Definition: bd.h:262
int GetInt() const
Definition: dt.h:581
Definition: tm.h:355
static PTimeNet New()
Definition: timenet.h:39
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:221
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:373
TNodeData & GetNDat(const int &NId)
Returns node data for the node of ID NId in the network.
Definition: network.h:229
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:189
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:219
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:217
void SplitOnCh(TStr &LStr, const char &SplitCh, TStr &RStr) const
Definition: dt.cpp:901
const char * GetTmStr() const
Definition: tm.h:370
virtual void DelNode(const int &NId)
Deletes node of ID NId from the network.
Definition: network.h:347
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the network.
Definition: network.h:381
void Tick()
Definition: tm.h:364
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
Definition: network.h:401
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:311
Definition: tm.h:81
Definition: dt.h:412
void SplitOnAllCh(const char &SplitCh, TStrV &StrV, const bool &SkipEmpty=true) const
Definition: dt.cpp:926
Definition: bd.h:196
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the network.
Definition: network.h:423
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a network of Nodes nodes and Edges edges.
Definition: network.h:278
char * CStr()
Definition: dt.h:479
int CntDegNodes(const PGraph &Graph, const int &NodeDeg)
Returns the number of nodes with degree NodeDeg.
Definition: alg.h:105
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
static PTimeNet TTimeNet::New ( )
inlinestatic

Definition at line 39 of file timenet.h.

39 { return new TTimeNet(); }
TTimeNet()
Definition: timenet.h:34
static PTimeNet TTimeNet::New ( const int &  Nodes,
const int &  Edges 
)
inlinestatic

Definition at line 40 of file timenet.h.

40 { return new TTimeNet(Nodes, Edges); }
TTimeNet()
Definition: timenet.h:34
TTimeNet & TTimeNet::operator= ( const TTimeNet TimeNet)

Definition at line 3 of file timenet.cpp.

3  {
4  if (this != &TimeNet) {
5  TNet::operator=(TimeNet);
6  }
7  return *this;
8 }
TNodeNet & operator=(const TNodeNet &NodeNet)
Definition: network.h:185
void TTimeNet::PlotCCfOverTm ( const TStr FNmPref,
TStr  Desc,
const TTmUnit TmUnit,
const int &  NodesBucket = -1 
) const

Definition at line 253 of file timenet.cpp.

253  {
254  if (Desc.Empty()) { Desc = FNmPref; }
255  TTimeNet::TTmBucketV TmBucketV;
256  TStr XLbl;
257  if (TmUnit == tmuNodes) {
258  XLbl = "Number of nodes (time)";
259  IAssert(NodesBucket > 0);
260  GetNodeBuckets(NodesBucket, TmBucketV); }
261  else {
262  XLbl = TStr::Fmt("Time (%s)", TTmInfo::GetTmUnitStr(TmUnit).CStr());
263  GetTmBuckets(TmUnit, TmBucketV);
264  }
265  TIntV NodeIdV;
266  TFltPrV DegToCCfV, CcfV, OpClV, OpV;
267  TVec<TTuple<TFlt, 4> > OpenClsV;
268  TTuple<TFlt, 4> Tuple;
269  TExeTm ExeTm;
270  int XVal = 0;
271  printf("Clustering coefficient over time:\n %d edges, %d edges per bucket, %d buckets \n", GetEdges(), 100000, TmBucketV.Len());
272  PUNGraph UNGraph = TSnap::ConvertGraph<PUNGraph>(PTimeNet((TTimeNet*)this));
273  for (int t = 0; t < TmBucketV.Len(); t++) {
274  printf("\r %d/%d: ", t+1, TmBucketV.Len());
275  NodeIdV.AddV(TmBucketV[t].NIdV); // edges up to time T
276  int64 Open=0, Close=0;
277  const PUNGraph Graph = TSnap::GetSubGraph(UNGraph, NodeIdV);
278  const double CCf = TSnap::GetClustCf(Graph, DegToCCfV, Open, Close);
279  if (TmUnit == tmuNodes) { XVal = Graph->GetNodes(); }
280  else { XVal = TmBucketV[t].BegTm.GetInUnits(TmUnit); }
281  CcfV.Add(TFltPr(XVal, CCf));
282  double FltOpen = static_cast<double>(Open);
283  double FltClose = static_cast<double>(Close);
284  OpClV.Add(TFltPr(XVal, (Open+Close==0 ? 0.0 : FltClose/(FltOpen+FltClose))));
285  OpV.Add(TFltPr(XVal, (Open==0 ? 0.0 : FltClose/FltOpen)));
286  Tuple[0]=Graph->GetNodes();
287  Tuple[1]=Graph->GetEdges();
288  Tuple[2]=FltClose; Tuple[3]=FltOpen;
289  OpenClsV.Add(Tuple);
290  printf(" %s", ExeTm.GetStr());
291  TGnuPlot::PlotValV(DegToCCfV, TStr::Fmt("ccfAt%02dtm.%s", t+1, FNmPref.CStr()),
292  TStr::Fmt("%s. At time %d. Clustering Coefficient. G(%d,%d)", Desc.CStr(), t+1, Graph->GetNodes(), Graph->GetEdges()),
293  "Degree", "Clustering coefficient", gpsLog10XY, false);
294  }
295  TGnuPlot::PlotValV(CcfV, "ccfOverTm."+FNmPref, Desc+". Average Clustering Coefficient", XLbl, "Average clustering coefficient", gpsAuto, false);
296  TGnuPlot::PlotValV(OpClV, "ClsOpnTr1."+FNmPref, Desc+". Close/(Open+Closed) triads", XLbl, "Close / (Open+Closed) triads", gpsAuto, false);
297  TGnuPlot::PlotValV(OpV, "ClsOpnTr2."+FNmPref, Desc+". Close/Open triads", XLbl, "Close / Open triads", gpsAuto, false);
298  TGnuPlot::SaveTs(OpenClsV, "ClsOpnTr."+FNmPref+".tab", TStr::Fmt("#%s\n#Nodes\tEdges\tClosed\tOpenTriads", Desc.CStr()));
299  printf("\n");
300 }
#define IAssert(Cond)
Definition: bd.h:262
Definition: tm.h:355
Definition: ds.h:272
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int GetEdges() const
Returns the number of edges in the network.
void GetTmBuckets(const TTmUnit &GroupBy, TTmBucketV &TmBucketV) const
Definition: timenet.cpp:59
Definition: gnuplot.h:7
static void SaveTs(const TIntKdV &KdV, const TStr &FNm, const TStr &HeadLn=TStr())
Definition: gnuplot.cpp:717
PUNGraph GetSubGraph(const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumb...
Definition: subgraph.cpp:7
Definition: tm.h:14
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
void GetNodeBuckets(const int NodesPerBucket, TTimeNet::TTmBucketV &TmBucketV) const
Definition: timenet.cpp:77
static TStr GetTmUnitStr(const TTmUnit &TmUnit)
Definition: tm.cpp:108
long long int64
Definition: bd.h:27
Definition: dt.h:412
bool Empty() const
Definition: dt.h:491
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
double GetClustCf(const PGraph &Graph, int SampleNodes=-1)
Computes the average clustering coefficient as defined in Watts and Strogatz, Collective dynamics of ...
Definition: triad.h:137
Definition: bd.h:196
TPt< TTimeNet > PTimeNet
Definition: timenet.h:8
const char * GetStr() const
Definition: tm.h:368
char * CStr()
Definition: dt.h:479
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
static void PlotValV(const TVec< TVal1 > &ValV, const TStr &OutFNmPref, const TStr &Desc="", const TStr &XLabel="", const TStr &YLabel="", const TGpScaleTy &ScaleTy=gpsAuto, const bool &PowerFit=false, const TGpSeriesTy &SeriesTy=gpwLinesPoints)
Definition: gnuplot.h:398
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
TSizeTy AddV(const TVec< TVal, TSizeTy > &ValV)
Adds the elements of the vector ValV to the to end of the vector.
Definition: ds.h:1110
void TTimeNet::PlotEffDiam ( const TStr FNmPref,
const TStr Desc,
const TTmUnit GroupBy,
const TSecTm StartTm,
const int &  NDiamRuns = 10,
const bool &  OnlyWcc = false,
const bool &  AlsoRewire = false 
) const

Definition at line 106 of file timenet.cpp.

107  {
108  const TStr WccStr = OnlyWcc ? "WCC " : TStr::GetNullStr();
109  TTmBucketV TmBucketV;
110  GetTmBuckets(TmUnit, TmBucketV);
111  TIntV NodeIdV;
112  TExeTm ExeTm, Run1Tm;
113  TFltTrV TmDiamV, NdsDiamV;
114  TFltTrV RwTmDiamV, RwNdsDiamV;
115  for (int t = 0; t < TmBucketV.Len(); t++) {
116  NodeIdV.AddV(TmBucketV[t].NIdV); // nodes up to time T
117  printf("\n*** %d/%d] at %s (%d nodes)\n", t+1, TmBucketV.Len(),
118  TmBucketV[t].BegTm.GetStr(TmUnit).CStr(), NodeIdV.Len()); ExeTm.Tick();
119  if (TmBucketV[t].BegTm < StartTm) continue;
120  //PUNGraph PreGraph = GetSubUNGraph(NodeIdV, true);
121  PUNGraph PreGraph = TSnap::ConvertSubGraph<PUNGraph>(PTimeNet((TTimeNet*)this), NodeIdV);
122  { TMom Mom;
123  for (int r = 0; r < NDiamRuns; r++) {
124  printf("%d...", r+1); Run1Tm.Tick();
125  const double EffDiam = TSnap::GetAnfEffDiam(OnlyWcc ? TSnap::GetMxWcc(PreGraph) : PreGraph);
126  Mom.Add(EffDiam); printf("[%s]\r", Run1Tm.GetTmStr());
127  }
128  Mom.Def();
129  TmDiamV.Add(TFltTr((int)TmBucketV[t].BegTm.GetInUnits(TmUnit), Mom.GetMean(), Mom.GetSDev()));
130  NdsDiamV.Add(TFltTr(PreGraph->GetNodes(), Mom.GetMean(), Mom.GetSDev()));
131  NdsDiamV.Sort();
132  printf(" [%s] \n", ExeTm.GetTmStr()); }
133  if (AlsoRewire) {
134  //PUNGraph RwGraph = TGGen::GenRndDegSeqS(PreGraph, 50, TInt::Rnd); // edge switching model
135  TIntV DegSeqV(PreGraph->GetNodes(), 0);
136  for (TUNGraph::TNodeI NI = PreGraph->BegNI(); NI < PreGraph->EndNI(); NI++) { DegSeqV.Add(NI.GetDeg()); }
137  PUNGraph RwGraph = TSnap::GenConfModel(DegSeqV, TInt::Rnd);
138  printf("Configuration model: (%d, %d) --> (%d, %d)\n", PreGraph->GetNodes(), PreGraph->GetEdges(), RwGraph->GetNodes(), RwGraph->GetEdges());
139  TMom Mom;
140  for (int r = 0; r < NDiamRuns; r++) {
141  printf(" diam run %d...", r+1); Run1Tm.Tick();
142  const double EffDiam = TSnap::GetAnfEffDiam(OnlyWcc ? TSnap::GetMxWcc(PreGraph):PreGraph);
143  Mom.Add(EffDiam); printf(" current run [%s]\n", Run1Tm.GetTmStr());
144  }
145  Mom.Def();
146  RwTmDiamV.Add(TFltTr((int)TmBucketV[t].BegTm.GetInUnits(TmUnit), Mom.GetMean(), Mom.GetSDev()));
147  RwNdsDiamV.Add(TFltTr(PreGraph->GetNodes(), Mom.GetMean(), Mom.GetSDev()));
148  RwNdsDiamV.Sort();
149  printf("done with diameter. Total time [%s] \n", ExeTm.GetTmStr());
150  }
151  // plot
152  { TGnuPlot GnuPlot("diamEff-T."+FNmPref, TStr::Fmt("%s. G(%d, %d)", Desc.CStr(), GetNodes(), GetEdges()));
153  GnuPlot.SetXYLabel(TStr::Fmt("TIME [%s]", TTmInfo::GetTmUnitStr(TmUnit).CStr()), WccStr+"Effective Diameter");
154  GnuPlot.AddErrBar(TmDiamV, "True", "");
155  if (! RwTmDiamV.Empty()) { GnuPlot.AddErrBar(RwTmDiamV, "Rewired", "");}
156  GnuPlot.SavePng(); }
157  { TGnuPlot GnuPlot("diamEff-N."+FNmPref, TStr::Fmt("%s. G(%d, %d)", Desc.CStr(), GetNodes(), GetEdges()));
158  GnuPlot.SetXYLabel("NODES", WccStr+"Effective Diameter");
159  GnuPlot.AddErrBar(NdsDiamV, "True", "");
160  if (! RwNdsDiamV.Empty()) { GnuPlot.AddErrBar(RwNdsDiamV, "Rewired", "");}
161  GnuPlot.SavePng(); }
162  }
163 }
Definition: tm.h:355
PGraph GetMxWcc(const PGraph &Graph)
Returns a graph representing the largest weakly connected component on an input Graph.
Definition: cncom.h:452
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
double GetAnfEffDiam(const PGraph &Graph, const bool &IsDir, const double &Percentile, const int &NApprox)
Definition: anf.h:216
int GetEdges() const
Returns the number of edges in the network.
void GetTmBuckets(const TTmUnit &GroupBy, TTmBucketV &TmBucketV) const
Definition: timenet.cpp:59
Definition: xmath.h:129
TVec< TTmBucket > TTmBucketV
Definition: timenet.h:32
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:189
static TRnd Rnd
Definition: dt.h:1146
double GetSDev() const
Definition: xmath.h:242
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
const char * GetTmStr() const
Definition: tm.h:370
void Add(const TFlt &Val, const TFlt &Wgt=1)
Definition: xmath.h:217
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TTriple< TFlt, TFlt, TFlt > TFltTr
Definition: ds.h:181
PUNGraph GenConfModel(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random undirect graph with a given degree sequence.
Definition: ggen.cpp:122
static TStr GetNullStr()
Definition: dt.cpp:1626
void Tick()
Definition: tm.h:364
static TStr GetTmUnitStr(const TTmUnit &TmUnit)
Definition: tm.cpp:108
double GetMean() const
Definition: xmath.h:240
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
Definition: bd.h:196
TPt< TTimeNet > PTimeNet
Definition: timenet.h:8
char * CStr()
Definition: dt.h:479
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void Def()
Definition: xmath.cpp:339
TSizeTy AddV(const TVec< TVal, TSizeTy > &ValV)
Adds the elements of the vector ValV to the to end of the vector.
Definition: ds.h:1110
void TTimeNet::PlotMedianDegOverTm ( const TStr FNmPref,
const TTmUnit TmUnit,
const int &  NodesPerBucket = -1 
) const

Definition at line 302 of file timenet.cpp.

302  {
303  TTimeNet::TTmBucketV TmBucketV;
304  TStr XLbl;
305  if (TmUnit == tmuNodes) {
306  XLbl = "Number of nodes (time)"; IAssert(NodesPerBucket > 0);
307  GetNodeBuckets(NodesPerBucket, TmBucketV); }
308  else {
309  XLbl = TStr::Fmt("Time (%s)", TTmInfo::GetTmUnitStr(TmUnit).CStr());
310  GetTmBuckets(TmUnit, TmBucketV); }
311  printf("\n\n%s\nMedian degree over time:\n %d edges, %d edges per bucket, %d buckets \n", FNmPref.CStr(), GetEdges(), NodesPerBucket, TmBucketV.Len());
312  TFltPrV MedDegV, MedInDegV, MedOutDegV;
313  TIntV NodeIdV;
314  int XVal;
315  PUNGraph UNGraph = TSnap::ConvertGraph<PUNGraph>(PTimeNet((TTimeNet*)this));
316  PNGraph NGraph = TSnap::ConvertGraph<PNGraph>(PTimeNet((TTimeNet*)this));
317  FILE *F = fopen(("gStat-"+FNmPref+".tab").CStr(), "wt");
318  fprintf(F, "UndirNodes\tUndirEdges\tUndirNonZNodes\tMedianDeg\tMeanDeg\tDirNodes\tDirEdges\tDirNonzNodes\tMedInDeg\tMedOutDeg\tMeanInDeg\tMeanOutDeg\n");
319  for (int t = 0; t < TmBucketV.Len(); t++) {
320  printf("\r %d/%d: ", t+1, TmBucketV.Len());
321  NodeIdV.AddV(TmBucketV[t].NIdV); // edges up to time T
322  if (TmUnit == tmuNodes) { XVal = NodeIdV.Len(); }
323  else { XVal = TmBucketV[t].BegTm.GetInUnits(TmUnit); }
324  // un graph
325  { const PUNGraph Graph = TSnap::GetSubGraph(UNGraph, NodeIdV); TMom Mom;
326  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) { if (NI.GetOutDeg()>0) { Mom.Add(NI.GetOutDeg());} }
327  Mom.Def(); MedDegV.Add(TFltPr(XVal, Mom.GetMedian()));
328  fprintf(F, "%d\t%d\t%d\t%f\t%f", Graph->GetNodes(), Graph->GetEdges(), TSnap::CntNonZNodes(Graph), (float)Mom.GetMedian(), (float)Mom.GetMean()); }
329  // directed graph
330  { const PNGraph Graph = TSnap::GetSubGraph<PNGraph>(NGraph, NodeIdV); TMom MomOut, MomIn;
331  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
332  if (NI.GetOutDeg()>0) { MomOut.Add(NI.GetOutDeg()); }
333  if (NI.GetInDeg()>0) { MomIn.Add(NI.GetInDeg()); } }
334  MomOut.Def(); MedOutDegV.Add(TFltPr(XVal, MomOut.GetMedian()));
335  MomIn.Def(); MedInDegV.Add(TFltPr(XVal, MomIn.GetMedian()));
336  fprintf(F, "\t%d\t%d\t%d\t%f\t%f\t%f\t%f\n", Graph->GetNodes(), Graph->GetEdges(), (int)TSnap::CntNonZNodes(Graph), (float)MomIn.GetMedian(), (float)MomOut.GetMedian(), (float)MomIn.GetMean(), (float)MomOut.GetMean()); }
337  }
338  fclose(F);
339  TGnuPlot::PlotValV(MedDegV, "medDeg."+FNmPref, FNmPref+" Median degree", TTmInfo::GetTmUnitStr(TmUnit), "Median degree");
340  TGnuPlot::PlotValV(MedOutDegV, "medOutDeg."+FNmPref, FNmPref+" Median OUT degree", TTmInfo::GetTmUnitStr(TmUnit), "Median OUT degree");
341  TGnuPlot::PlotValV(MedInDegV, "medInDeg."+FNmPref, FNmPref+" Median IN degree", TTmInfo::GetTmUnitStr(TmUnit), "Median IN degree");
342 }
#define IAssert(Cond)
Definition: bd.h:262
double GetMedian() const
Definition: xmath.h:244
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
int GetEdges() const
Returns the number of edges in the network.
void GetTmBuckets(const TTmUnit &GroupBy, TTmBucketV &TmBucketV) const
Definition: timenet.cpp:59
Definition: xmath.h:129
void Add(const TFlt &Val, const TFlt &Wgt=1)
Definition: xmath.h:217
int CntNonZNodes(const PGraph &Graph)
Returns the number of nodes with degree greater than 0.
Definition: alg.h:114
PUNGraph GetSubGraph(const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumb...
Definition: subgraph.cpp:7
Definition: tm.h:14
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
void GetNodeBuckets(const int NodesPerBucket, TTimeNet::TTmBucketV &TmBucketV) const
Definition: timenet.cpp:77
static TStr GetTmUnitStr(const TTmUnit &TmUnit)
Definition: tm.cpp:108
double GetMean() const
Definition: xmath.h:240
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
Definition: bd.h:196
TPt< TTimeNet > PTimeNet
Definition: timenet.h:8
char * CStr()
Definition: dt.h:479
static void PlotValV(const TVec< TVal1 > &ValV, const TStr &OutFNmPref, const TStr &Desc="", const TStr &XLabel="", const TStr &YLabel="", const TGpScaleTy &ScaleTy=gpsAuto, const bool &PowerFit=false, const TGpSeriesTy &SeriesTy=gpwLinesPoints)
Definition: gnuplot.h:398
void Def()
Definition: xmath.cpp:339
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
TSizeTy AddV(const TVec< TVal, TSizeTy > &ValV)
Adds the elements of the vector ValV to the to end of the vector.
Definition: ds.h:1110
void TTimeNet::PlotMissingPast ( const TStr FNmPref,
const TStr Desc,
const TTmUnit GroupBy,
const TSecTm DelPreTmEdges,
const TSecTm PostTmDiam 
) const

Definition at line 169 of file timenet.cpp.

170  {
171  printf("\nGrowth over time: degree distribution, Growth Power Law, Diameter.\n %s group by %s.\n",
172  FNmPref.CStr(), TTmInfo::GetTmUnitStr(TmUnit).CStr());
173  printf(" Delete out-edges of pre time %s nodes.\n Take subgraph of post year %s subgraph.\n\n",
174  DelPreTmEdges.GetStr().CStr(), PostTmDiam.GetStr().CStr());
175  const int NDiamRuns = 10;
176  const int NSamples = 100;
177  //PUNGraph FullGraph = GetUNGraph();
178  PUNGraph FullGraph = TSnap::ConvertGraph<PUNGraph>(PTimeNet((TTimeNet*)this));
179  // delete past
180  if (DelPreTmEdges.IsDef()) {
181  int NDelNodes = 0, NDelEdges = 0;
182  printf("Deleting pre-%s node out-links\n", DelPreTmEdges.GetStr().CStr());
183  for (TNodeI NodeI = BegNI(); NodeI < EndNI(); NodeI++) {
184  if (NodeI() < DelPreTmEdges) {
185  const int NodeId = NodeI.GetId();
186  for (int edge = 0; edge < NodeI.GetOutDeg(); edge++) {
187  FullGraph->DelEdge(NodeId, NodeI.GetOutNId(edge)); }
188  NDelEdges += NodeI.GetOutDeg(); NDelNodes++;
189  }
190  }
191  printf(" Deleted %d nodes out-edges (%d edges total).\n", NDelNodes, NDelEdges);
192  FullGraph->Defrag(true);
193  }
194  PGStatVec GrowthStat = TGStatVec::New(TmUnit);
195  TFltV PreDiamSDev, PreEffDiamSDev, WccDiamSDev, WccEffDiamSDev;
196  TIntV NodeIdV;
197  TExeTm ExeTm;
198  TTmBucketV TmBucketV;
199  GetTmBuckets(TmUnit, TmBucketV);
200  for (int t = 0; t < TmBucketV.Len(); t++) {
201  printf("\nGraph: %s (%d / %d) [%s]\n", TmBucketV[t].BegTm.GetTmStr().CStr(),
202  t+1, TmBucketV.Len(), TExeTm::GetCurTm());
203  // up-to-year subgraph
204  NodeIdV.AddV(TmBucketV[t].NIdV); // nodes up to time T
205  if (TmBucketV[t].BegTm < PostTmDiam) { continue; }
206  const PUNGraph PreGraph = TSnap::GetSubGraph(FullGraph, NodeIdV, true);
207  const PUNGraph WccGraph = TSnap::GetMxWcc(PreGraph);
208  TIntV PostYearNIdV, WccPostYearNIdV;
209  for (TUNGraph::TNodeI NI = PreGraph->BegNI(); NI < PreGraph->EndNI(); NI++) {
210  if (GetNDat(NI.GetId()) >= PostTmDiam) {
211  PostYearNIdV.Add(NI.GetId());
212  if (WccGraph->IsNode(NI.GetId())) { WccPostYearNIdV.Add(NI.GetId()); }
213  }
214  }
215  TMom PreDiamMom, PreEffDiamMom, WccDiamMom, WccEffDiamMom;
216  // diameter of PostYearDiam subgraph using whole graph (all edges)
217  int FullDiam; double EffDiam;
218  for (int r = 0; r < NDiamRuns; r++) {
219  if (! PostYearNIdV.Empty()) {
220  TSnap::GetBfsEffDiam(PreGraph, NSamples, PostYearNIdV, false, EffDiam, FullDiam);
221  PreDiamMom.Add(FullDiam); PreEffDiamMom.Add(EffDiam);
222  }
223  if (! WccPostYearNIdV.Empty()) {
224  TSnap::GetBfsEffDiam(WccGraph, NSamples, WccPostYearNIdV, false, EffDiam, FullDiam);
225  WccDiamMom.Add(FullDiam); WccEffDiamMom.Add(EffDiam);
226  }
227  printf(" diam: %d [%s] \r", r+1, ExeTm.GetTmStr()); ExeTm.Tick();
228  }
229  PreDiamMom.Def(); PreEffDiamMom.Def();
230  WccDiamMom.Def(); WccEffDiamMom.Def();
231  // save stat
232  PGStat GraphStatPt = GrowthStat->Add(TmBucketV[t].BegTm);
233  TGStat& GS = *GraphStatPt;
234  GS.TakeBasicStat(PreGraph, false);
235  GS.TakeBasicStat(WccGraph, true);
236  GS.SetVal(gsvFullDiam, PreDiamMom.GetMean()); // mean
237  GS.SetVal(gsvEffDiam, PreEffDiamMom.GetMean());
238  GS.SetVal(gsvFullWccDiam, WccDiamMom.GetMean());
239  GS.SetVal(gsvEffWccDiam, WccEffDiamMom.GetMean());
240  GS.SetVal(gsvFullDiamDev, PreDiamMom.GetSDev()); // variance
241  GS.SetVal(gsvEffDiamDev, PreEffDiamMom.GetSDev());
242  GS.SetVal(gsvFullWccDiamDev, WccDiamMom.GetSDev());
243  GS.SetVal(gsvEffWccDiamDev, WccEffDiamMom.GetSDev());
244  { TFOut FOut("growth."+FNmPref+".gStatVec"); GrowthStat->Save(FOut); }
245  GrowthStat->SaveTxt(FNmPref, TStr::Fmt("%s. MISSING PAST DIAMETER\nDelPreEdges\t%s\nPostYearDiam\t%s\n",
246  Desc.CStr(), DelPreTmEdges.GetStr().CStr(), PostTmDiam.GetStr().CStr()));
247  }
248  // diameter plots
249  //GrowthStat->PlotDiam(FNmPref, Desc + TStr::Fmt(" MISSING PAST. DelPre:%d PostYear:%d.",
250  // DelPreEdges, PostYearDiam));*/
251 }
static char * GetCurTm()
Definition: tm.h:374
Definition: tm.h:355
bool IsDef() const
Definition: tm.h:123
double GetBfsEffDiam(const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false)
Returns the (approximation of the) Effective Diameter (90-th percentile of the distribution of shorte...
Definition: bfsdfs.h:424
PGraph GetMxWcc(const PGraph &Graph)
Returns a graph representing the largest weakly connected component on an input Graph.
Definition: cncom.h:452
Definition: fl.h:319
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:221
void GetTmBuckets(const TTmUnit &GroupBy, TTmBucketV &TmBucketV) const
Definition: timenet.cpp:59
Definition: xmath.h:129
TVec< TTmBucket > TTmBucketV
Definition: timenet.h:32
TSecTm & GetNDat(const int &NId)
Returns node data for the node of ID NId in the network.
Definition: network.h:229
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:219
double GetSDev() const
Definition: xmath.h:242
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
const char * GetTmStr() const
Definition: tm.h:370
void Add(const TFlt &Val, const TFlt &Wgt=1)
Definition: xmath.h:217
Statistics of a Graph Snapshot.
Definition: gstat.h:36
PUNGraph GetSubGraph(const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumb...
Definition: subgraph.cpp:7
void Tick()
Definition: tm.h:364
void SetVal(const TGStatVal &StatVal, const double &Val)
Definition: gstat.cpp:88
static TStr GetTmUnitStr(const TTmUnit &TmUnit)
Definition: tm.cpp:108
double GetMean() const
Definition: xmath.h:240
void Save(TSOut &SOut) const
Definition: xmlser.h:16
TStr GetStr(const TLoc &Loc=lUs) const
Definition: tm.cpp:457
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
Definition: bd.h:196
TPt< TTimeNet > PTimeNet
Definition: timenet.h:8
char * CStr()
Definition: dt.h:479
static PGStatVec New(const TTmUnit &_TmUnit=tmu1Sec)
Definition: gstat.cpp:426
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void Def()
Definition: xmath.cpp:339
TSizeTy AddV(const TVec< TVal, TSizeTy > &ValV)
Adds the elements of the vector ValV to the to end of the vector.
Definition: ds.h:1110
void TakeBasicStat(const PGraph &Graph, const bool &IsMxWcc=false)
Definition: gstat.h:257
void TTimeNet::Save ( TSOut SOut) const
inlinevirtual

Saves the network to a (binary) stream SOut.

Reimplemented from TNodeNet< TSecTm >.

Definition at line 38 of file timenet.h.

38 { TNet::Save(SOut); }
virtual void Save(TSOut &SOut) const
Saves the network to a (binary) stream SOut.
Definition: network.h:168
PGStatVec TTimeNet::TimeGrowth ( const TTmUnit TmUnit,
const TFSet TakeStat,
const TSecTm StartTm 
) const

Definition at line 88 of file timenet.cpp.

88  {
89  PGStatVec GrowthStat = new TGStatVec(TmUnit, TakeStat);
90  TTmBucketV TmBucketV;
91  GetTmBuckets(TmUnit, TmBucketV);
92  TIntV NodeIdV;
93  TExeTm ExeTm;
94  for (int t = 0; t < TmBucketV.Len(); t++) {
95  NodeIdV.AddV(TmBucketV[t].NIdV); // nodes up to time T
96  printf("\n=== %d/%d] %s (%d nodes)\n", t+1, TmBucketV.Len(),
97  TmBucketV[t].BegTm.GetStr().CStr(), NodeIdV.Len()); ExeTm.Tick();
98  if (TmBucketV[t].BegTm < StartTm) continue;
99  //PNGraph PreGraph = GetSubGraph(NodeIdV, true); // renumber nodes
100  PNGraph PreGraph = TSnap::ConvertSubGraph<PNGraph>(PTimeNet((TTimeNet*)this), NodeIdV); // don't renumber nodes
101  GrowthStat->Add(PreGraph, TmBucketV[t].BegTm);
102  }
103  return GrowthStat;
104 }
Definition: tm.h:355
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void GetTmBuckets(const TTmUnit &GroupBy, TTmBucketV &TmBucketV) const
Definition: timenet.cpp:59
TVec< TTmBucket > TTmBucketV
Definition: timenet.h:32
Graph Statistics Sequence.
Definition: gstat.h:155
void Tick()
Definition: tm.h:364
Definition: bd.h:196
TPt< TTimeNet > PTimeNet
Definition: timenet.h:8
TSizeTy AddV(const TVec< TVal, TSizeTy > &ValV)
Adds the elements of the vector ValV to the to end of the vector.
Definition: ds.h:1110

Friends And Related Function Documentation

friend class TPt< TTimeNet >
friend

Definition at line 65 of file timenet.h.


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