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
cascnetinf.cpp
Go to the documentation of this file.
1 #include "stdafx.h"
2 #include "cascnetinf.h"
3 
4 double TCascade::TransProb(const int& NId1, const int& NId2) const {
5  if (!IsNode(NId1) || !IsNode(NId2)) { return Eps.Val; }
6  if (GetTm(NId1) >= GetTm(NId2)) { return Eps.Val; }
7  if (Model==0)
8  return Alpha*exp(-Alpha*(GetTm(NId2)-GetTm(NId1))); // exponential
9  else if (Model==1)
10  return (Alpha-1)*pow((GetTm(NId2)-GetTm(NId1)), -Alpha); // power-law
11  else
12  return Alpha*(GetTm(NId2)-GetTm(NId1))*exp(-0.5*Alpha*pow(GetTm(NId2)-GetTm(NId1), 2)); // rayleigh
13 
14  return (-1);
15 }
16 
17 double TCascade::GetProb(const PNGraph& G) {
18  double P = 0;
19  for (int n = 0; n < Len(); n++) {
20  const int DstNId = GetNode(n);
21  const double DstTm = GetTm(DstNId);
22  TNGraph::TNodeI NI = G->GetNI(DstNId);
23  double MxProb = log(Eps);
24  int BestParent = -1;
25  for (int e = 0; e < NI.GetInDeg(); e++) {
26  const int SrcNId = NI.GetInNId(e);
27  if (IsNode(SrcNId) && GetTm(SrcNId) < DstTm) {
28  const double Prob = log(TransProb(SrcNId, DstNId));
29  if (MxProb < Prob) { MxProb = Prob; BestParent = SrcNId; }
30  }
31  }
32  NIdHitH.GetDat(DstNId).Parent = BestParent;
33  P += MxProb;
34  }
35 
36  return P;
37 }
38 
39 // init prob of a cascade in an empty graph
41  CurProb = log(Eps) * Len();
42  for (int i = 0; i < Len(); i++) {
43  NIdHitH[i].Parent = -1; }
44 }
45 
46 // update the cascade probability given a new edge (N1, N2) in the graph
47 double TCascade::UpdateProb(const int& N1, const int& N2, const bool& UpdateProb) {
48  if (!IsNode(N1) || !IsNode(N2)) { return CurProb; }
49  if (GetTm(N1) >= GetTm(N2)) { return CurProb; }
50  const double P1 = log(TransProb(GetParent(N2), N2));
51  const double P2 = log(TransProb(N1, N2)); // N1 influences N2
52  if (P1 < P2) {
53  if (UpdateProb) { // the edge is there, update the CurProb and best Parent
54  CurProb = CurProb - P1 + P2;
55  NIdHitH.GetDat(N2).Parent = N1;
56  } else {
57  return CurProb - P1 + P2; }
58  }
59  return CurProb;
60 }
61 
62 void TNetInfBs::LoadCascadesTxt(TSIn& SIn, const int& Model, const double& alpha) {
63  TStr Line;
64  while (!SIn.Eof()) {
65  SIn.GetNextLn(Line);
66  if (Line=="") { break; }
67  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
68  AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0));
69  }
70  printf("All nodes read!\n");
71  while (!SIn.Eof()) { SIn.GetNextLn(Line); AddCasc(Line, Model, alpha); }
72  printf("All cascades read!\n");
73 }
74 
76  GroundTruth = TNGraph::New(); TStr Line;
77 
78  // add nodes
79  while (!SIn.Eof()) {
80  SIn.GetNextLn(Line);
81  if (Line=="") { break; }
82  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
83  GroundTruth->AddNode(NIdV[0].GetInt());
84  }
85 
86  // add edges
87  while (!SIn.Eof()) {
88  SIn.GetNextLn(Line);
89  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
90  GroundTruth->AddEdge(NIdV[0].GetInt(), NIdV[1].GetInt());
91  if (NIdV.Len()>2) { Alphas.AddDat(TIntPr(NIdV[0].GetInt(), NIdV[1].GetInt())) = NIdV[2].GetFlt(); }
92  else { Alphas.AddDat(TIntPr(NIdV[0].GetInt(), NIdV[1].GetInt())) = 1.0; }
93  }
94 
95  printf("groundtruth nodes:%d edges:%d\n", GroundTruth->GetNodes(), GroundTruth->GetEdges());
96 }
97 
98 void TNetInfBs::AddCasc(const TStr& CascStr, const int& Model, const double& alpha) {
99  TStrV NIdV; CascStr.SplitOnAllCh(',', NIdV);
100  TCascade C(alpha, Model);
101  for (int i = 0; i < NIdV.Len(); i+=2) {
102  int NId;
103  double Tm;
104  NId = NIdV[i].GetInt();
105  Tm = NIdV[i+1].GetFlt();
106  GetNodeInfo(NId).Vol = GetNodeInfo(NId).Vol + 1;
107  C.Add(NId, Tm);
108  }
109  C.Sort();
110  CascV.Add(C);
111 }
112 
113 void TNetInfBs::GenCascade(TCascade& C, const int& TModel, const double &window, TIntPrIntH& EdgesUsed, const double& delta,
114  const double& std_waiting_time, const double& std_beta) {
115  TIntFltH InfectedNIdH; TIntH InfectedBy;
116  double GlobalTime; int StartNId;
117  double alpha, beta;
118 
119  if (GroundTruth->GetNodes() == 0)
120  return;
121 
122  while (C.Len() < 2) {
123  C.Clr();
124  InfectedNIdH.Clr();
125  InfectedBy.Clr();
126  GlobalTime = 0;
127 
128  StartNId = GroundTruth->GetRndNId();
129  InfectedNIdH.AddDat(StartNId) = GlobalTime;
130 
131  while (true) {
132  // sort by time & get the oldest node that did not run infection
133  InfectedNIdH.SortByDat(true);
134  const int& NId = InfectedNIdH.BegI().GetKey();
135  GlobalTime = InfectedNIdH.BegI().GetDat();
136 
137  // all the nodes has run infection
138  if (GlobalTime >= window)
139  break;
140 
141  // add current oldest node to the network and set its time
142  C.Add(NId, GlobalTime);
143 
144  // run infection from the current oldest node
145  const TNGraph::TNodeI NI = GroundTruth->GetNI(NId);
146  for (int e = 0; e < NI.GetOutDeg(); e++) {
147  const int DstNId = NI.GetOutNId(e);
148 
149  beta = Betas.GetDat(TIntPr(NId, DstNId));
150 
151  // flip biased coin (set by beta)
152  if (TInt::Rnd.GetUniDev() > beta+std_beta*TFlt::Rnd.GetNrmDev())
153  continue;
154 
155  alpha = Alphas.GetDat(TIntPr(NId, DstNId));
156 
157  // not infecting the parent
158  if (InfectedBy.IsKey(NId) && InfectedBy.GetDat(NId).Val == DstNId)
159  continue;
160 
161  double sigmaT;
162  switch (TModel) {
163  case 0:
164  // exponential with alpha parameter
165  sigmaT = TInt::Rnd.GetExpDev(alpha);
166  break;
167  case 1:
168  // power-law with alpha parameter
169  sigmaT = TInt::Rnd.GetPowerDev(alpha);
170  while (sigmaT < delta) { sigmaT = TInt::Rnd.GetPowerDev(alpha); }
171  break;
172  case 2:
173  // rayleigh with alpha parameter
174  sigmaT = TInt::Rnd.GetRayleigh(1/sqrt(alpha));
175  break;
176  default:
177  sigmaT = 1;
178  break;
179  }
180 
181  // avoid negative time diffs in case of noise
182  if (std_waiting_time > 0)
183  sigmaT = TFlt::GetMx(0.0, sigmaT + std_waiting_time*TFlt::Rnd.GetNrmDev());
184 
185  double t1 = GlobalTime + sigmaT;
186 
187  if (InfectedNIdH.IsKey(DstNId)) {
188  double t2 = InfectedNIdH.GetDat(DstNId);
189  if (t2 > t1 && t2 != window) {
190  InfectedNIdH.GetDat(DstNId) = t1;
191  InfectedBy.GetDat(DstNId) = NId;
192  }
193  } else {
194  InfectedNIdH.AddDat(DstNId) = t1;
195  InfectedBy.AddDat(DstNId) = NId;
196  }
197  }
198 
199  // we cannot delete key (otherwise, we cannot sort), so we assign a big time (window cut-off)
200  InfectedNIdH.GetDat(NId) = window;
201  }
202 
203  }
204 
205  C.Sort();
206 
207  for (TIntH::TIter EI = InfectedBy.BegI(); EI < InfectedBy.EndI(); EI++) {
208  TIntPr Edge(EI.GetDat().Val, EI.GetKey().Val);
209 
210  if (!EdgesUsed.IsKey(Edge)) EdgesUsed.AddDat(Edge) = 0;
211 
212  EdgesUsed.GetDat(Edge) += 1;
213  }
214 }
215 
217  THash<TInt, TIntV> CascPN;
218  Graph = TNGraph::New();
219 
220  // reset vectors
221  EdgeGainV.Clr();
222  CascPerEdge.Clr();
224 
225  for (int c = 0; c < CascV.Len(); c++) {
226  for (int i = 0; i < CascV[c].Len(); i++) {
227  if (!Graph->IsNode(CascV[c].GetNode(i))) Graph->AddNode(CascV[c].GetNode(i));
228  if (!CascPN.IsKey(CascV[c].GetNode(i))) CascPN.AddDat(CascV[c].GetNode(i)) = TIntV();
229  CascPN.GetDat(CascV[c].GetNode(i)).Add(c);
230  }
231  CascV[c].InitProb();
232  }
233 
234  // only add edges that make sense (i.e., at least once coherent in time)
235  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
236  TIntV &Cascs = CascPN.GetDat(NI.GetId());
237  for (int c = 0; c < Cascs.Len(); c++) {
238  for (int i=0; i < CascV[Cascs[c]].Len(); i++) {
239  if (CascV[Cascs[c]].GetNode(i)==NI.GetId())
240  continue;
241 
242  if (CascV[Cascs[c]].GetTm(CascV[Cascs[c]].GetNode(i)) < CascV[Cascs[c]].GetTm(NI.GetId()) ) {
243  if (!CascPerEdge.IsKey(TIntPr(CascV[Cascs[c]].GetNode(i), NI.GetId()))) {
244  EdgeGainV.Add(TPair<TFlt, TIntPr>(TFlt::Mx, TIntPr(CascV[Cascs[c]].GetNode(i), NI.GetId())));
245  CascPerEdge.AddDat(TIntPr(CascV[Cascs[c]].GetNode(i), NI.GetId())) = TIntV();
246  }
247  // Add cascade to hash of cascades per edge (to implement localized update)
248  CascPerEdge.GetDat(TIntPr(CascV[Cascs[c]].GetNode(i), NI.GetId())).Add(Cascs[c]);
249  }
250  }
251  }
252  }
253 }
254 
255 double TNetInfBs::GetAllCascProb(const int& EdgeN1, const int& EdgeN2) {
256  double P = 0.0;
257 
258  if (EdgeN1==-1 && EdgeN2==-1) {
259  for (int c = 0; c < CascV.Len(); c++) {
260  P += CascV[c].UpdateProb(EdgeN1, EdgeN2, false); } // initial log-likelihood
261  return P;
262  }
263 
264  TIntV &CascsEdge = CascPerEdge.GetDat(TIntPr(EdgeN1, EdgeN2)); // only check cascades that contain the edge
265 
266  for (int c = 0; c < CascsEdge.Len(); c++) {
267  P += (CascV[CascsEdge[c]].UpdateProb(EdgeN1, EdgeN2, false) - CascV[CascsEdge[c]].CurProb); } // marginal gain
268  return P;
269 }
270 
271 TIntPr TNetInfBs::GetBestEdge(double& CurProb, double& LastGain, bool& msort, int &attempts) {
272  TIntPr BestE;
273  TVec<TInt> KeysV;
274  TVec<TPair<TFlt, TIntPr> > EdgeGainCopyToSortV;
275  TIntV EdgeZero;
276  double BestGain = TFlt::Mn;
277  int BestGainIndex = -1;
278 
279  if (msort) {
280  for (int i=0; i<TMath::Mn(attempts-1, EdgeGainV.Len()); i++)
281  EdgeGainCopyToSortV.Add(EdgeGainV[i]);
282 
283  // printf("Sorting sublist of size %d of marginal gains!\n", EdgeGainCopyToSortV.Len());
284 
285  // sort this list
286  EdgeGainCopyToSortV.Sort(false);
287 
288  // printf("Sublist sorted!\n");
289 
290  // clever way of resorting without need to copy (google interview question! :-))
291  for (int i=0, ii=0, j=0; ii < EdgeGainCopyToSortV.Len(); j++) {
292  if ( (i+EdgeGainCopyToSortV.Len() < EdgeGainV.Len()) && (EdgeGainCopyToSortV[ii].Val1 < EdgeGainV[i+EdgeGainCopyToSortV.Len()].Val1) ) {
293  EdgeGainV[j] = EdgeGainV[i+EdgeGainCopyToSortV.Len()];
294  i++;
295  } else {
296  EdgeGainV[j] = EdgeGainCopyToSortV[ii];
297  ii++;
298  }
299  }
300  }
301 
302  attempts = 0;
303 
304  for (int e = 0; e < EdgeGainV.Len(); e++) {
305  const TIntPr& Edge = EdgeGainV[e].Val2;
306  if (Graph->IsEdge(Edge.Val1, Edge.Val2)) { continue; } // if edge was already included in the graph
307 
308  const double EProb = GetAllCascProb(Edge.Val1, Edge.Val2);
309  EdgeGainV[e].Val1 = EProb; // update marginal gain
310  if (BestGain < EProb) {
311  BestGain = EProb;
312  BestGainIndex = e;
313  BestE = Edge;
314  }
315 
316  // if we only update one weight, we don't need to sort the list
317  attempts++;
318 
319  // keep track of zero edges after sorting once the full list
320  if (!Graph->IsEdge(Edge.Val1, Edge.Val2) && Graph->GetEdges() > 1) {
321  if (EProb == 0)
322  EdgeZero.Add(e);
323  }
324 
325  // lazy evaluation
326  if (e+1 == EdgeGainV.Len() || BestGain >= EdgeGainV[e+1].Val1) {
327  CurProb += BestGain;
328 
329  if (BestGain == 0)
330  return TIntPr(-1, -1);
331 
332  EdgeGainV.Del(BestGainIndex);
333 
334  // we know the edges in 0 will be in sorted order, so we start from the biggest
335  for (int i=EdgeZero.Len()-1; i>=0; i--) {
336  if (EdgeZero[i] > BestGainIndex)
337  EdgeGainV.Del(EdgeZero[i]-1);
338  else
339  EdgeGainV.Del(EdgeZero[i]);
340  }
341 
342  if (EdgeZero.Len() > 2) { attempts -= (EdgeZero.Len()-1); }
343 
344  msort = (attempts > 1);
345 
346  LastGain = BestGain;
347 
348  return BestE;
349  }
350  }
351 
352  printf("Edges exhausted!\n");
353  return TIntPr(-1, -1);
354 }
355 
356 double TNetInfBs::GetBound(const TIntPr& Edge, double& CurProb) {
357  double Bound = 0;
358  TFltV Bounds;
359 
360  // bound could be computed faster (using lazy evaluation, as in the optimization procedure)
361  for (int e=0; e < EdgeGainV.Len(); e++) {
362  const TIntPr& EE = EdgeGainV[e].Val2;
363  if (EE != Edge && !Graph->IsEdge(EE.Val1, EE.Val2)) {
364  const double EProb = GetAllCascProb(EE.Val1, EE.Val2);
365  if (EProb > CurProb) Bounds.Add(EProb - CurProb); }
366  }
367 
368  Bounds.Sort(false);
369  for (int i=0; i<Graph->GetEdges() && i<Bounds.Len(); i++) Bound += Bounds[i];
370 
371  return Bound;
372 }
373 
374 void TNetInfBs::GreedyOpt(const int& MxEdges) {
375  double CurProb = GetAllCascProb(-1, -1);
376  double LastGain = TFlt::Mx;
377  int attempts = 0;
378  bool msort = false;
379 
380  for (int k = 0; k < MxEdges && EdgeGainV.Len() > 0; k++) {
381  const TIntPr BestE = GetBestEdge(CurProb, LastGain, msort, attempts);
382  if (BestE == TIntPr(-1, -1)) // if we cannot add more edges, we stop
383  break;
384 
385  if (CompareGroundTruth) {
386  double precision = 0, recall = 0;
387  if (PrecisionRecall.Len() > 1) {
388  precision = PrecisionRecall[PrecisionRecall.Len()-1].Val2.Val;
389  recall = PrecisionRecall[PrecisionRecall.Len()-1].Val1.Val;
390  }
391  if (GroundTruth->IsEdge(BestE.Val1, BestE.Val2)) {
392  recall++;
393  } else {
394  precision++;
395  }
396 
397  PrecisionRecall.Add(TPair<TFlt, TFlt>(recall, precision));
398  }
399 
400  Graph->AddEdge(BestE.Val1, BestE.Val2); // add edge to network
401 
402 
403  // localized update!
404  TIntV &CascsEdge = CascPerEdge.GetDat(BestE); // only check cascades that contain the edge
405  for (int c = 0; c < CascsEdge.Len(); c++) {
406  CascV[CascsEdge[c]].UpdateProb(BestE.Val1, BestE.Val2, true); // update probabilities
407  }
408 
409  // some extra info for the added edge
410  TInt Vol; TFlt AverageTimeDiff; TFltV TimeDiffs;
411  Vol = 0; AverageTimeDiff = 0;
412  for (int i=0; i< CascV.Len(); i++) {
413  if (CascV[i].IsNode(BestE.Val2) && CascV[i].GetParent(BestE.Val2) == BestE.Val1) {
414  Vol += 1; TimeDiffs.Add(CascV[i].GetTm(BestE.Val2)-CascV[i].GetTm(BestE.Val1));
415  AverageTimeDiff += TimeDiffs[TimeDiffs.Len()-1]; }
416  }
417  AverageTimeDiff /= Vol;
418  if (TimeDiffs.Len() > 0)
419  TimeDiffs.Sort();
420  else
421  TimeDiffs.Add(0);
422 
423  // compute bound only if explicitly required
424  EdgeInfoH.AddDat(BestE) = TEdgeInfo(Vol,
425  LastGain,
426  0.0,
427  TimeDiffs[(int)(TimeDiffs.Len()/2)],
428  AverageTimeDiff);
429  }
430 
431  if (CompareGroundTruth) {
432  for (int i=0; i<PrecisionRecall.Len(); i++) {
433  PrecisionRecall[i].Val2 = 1.0 - PrecisionRecall[i].Val2/(PrecisionRecall[i].Val2+PrecisionRecall[i].Val1);
434  PrecisionRecall[i].Val1 /= (double)GroundTruth->GetEdges();
435  }
436  }
437 }
438 
439 void TNetInfBs::SavePajek(const TStr& OutFNm) {
440  TIntSet NIdSet;
441  FILE *F = fopen(OutFNm.CStr(), "wt");
442  fprintf(F, "*Vertices %d\r\n", NIdSet.Len());
443  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
444  const TNodeInfo& I = NI.GetDat();
445  fprintf(F, "%d \"%s\" ic Blue x_fact %f y_fact %f\r\n", NI.GetKey().Val,
446  I.Name.CStr(), TMath::Mx<double>(log((double)I.Vol)-5,1), TMath::Mx<double>(log((double)I.Vol)-5,1));
447  }
448  fprintf(F, "*Arcs\r\n");
449  for (TNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
450  fprintf(F, "%d %d 1\r\n", EI.GetSrcNId(), EI.GetDstNId());
451  }
452  fclose(F);
453 }
454 
455 void TNetInfBs::SavePlaneTextNet(const TStr& OutFNm) {
456  TIntSet NIdSet;
457  FILE *F = fopen(OutFNm.CStr(), "wt");
458  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
459  fprintf(F, "%d,%d\r\n", NI.GetKey().Val, NI.GetKey().Val);
460  }
461 
462  fprintf(F, "\r\n");
463 
464  for (TNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
465  fprintf(F, "%d,%d\r\n", EI.GetSrcNId(), EI.GetDstNId());
466  }
467  fclose(F);
468 }
469 
470 void TNetInfBs::SaveEdgeInfo(const TStr& OutFNm) {
471  FILE *F = fopen(OutFNm.CStr(), "wt");
472 
473  fprintf(F, "src dst vol marginal_gain median_timediff average_timediff\n");
474  for (THash<TIntPr, TEdgeInfo>::TIter EI = EdgeInfoH.BegI(); EI < EdgeInfoH.EndI(); EI++) {
475  TEdgeInfo &EdgeInfo = EI.GetDat();
476  fprintf(F, "%s/%s/%d/%f/%f/%f\n",
477  NodeNmH.GetDat(EI.GetKey().Val1.Val).Name.CStr(), NodeNmH.GetDat(EI.GetKey().Val2.Val).Name.CStr(),
478  EdgeInfo.Vol.Val, EdgeInfo.MarginalGain.Val,
479  EdgeInfo.MedianTimeDiff.Val,
480  EdgeInfo.AverageTimeDiff.Val);
481  }
482  fclose(F);
483 }
484 
485 void TNetInfBs::SaveObjInfo(const TStr& OutFNm) {
486  TGnuPlot GnuPlot(OutFNm);
487 
488  TFltV Objective;
489 
490  for (THash<TIntPr, TEdgeInfo>::TIter EI = EdgeInfoH.BegI(); EI < EdgeInfoH.EndI(); EI++) {
491  if (Objective.Len()==0) { Objective.Add(EI.GetDat().MarginalGain);
492  } else {
493  Objective.Add(Objective[Objective.Len()-1]+EI.GetDat().MarginalGain);
494  }
495  }
496 
497  GnuPlot.AddPlot(Objective, gpwLinesPoints);
498 
499  GnuPlot.SavePng();
500 }
501 
502 void TNetInfBs::SaveGroundTruth(const TStr& OutFNm) {
503  TFOut FOut(OutFNm);
504 
505  // write nodes to file
506  for (TNGraph::TNodeI NI = GroundTruth->BegNI(); NI < GroundTruth->EndNI(); NI++) {
507  FOut.PutStr(TStr::Fmt("%d,%d\r\n", NI.GetId(), NI.GetId())); // nodes
508  }
509 
510  FOut.PutStr("\r\n");
511 
512  // write edges to file (not allowing self loops in the network)
513  for (TNGraph::TEdgeI EI = GroundTruth->BegEI(); EI < GroundTruth->EndEI(); EI++) {
514  // not allowing self loops in the Kronecker network
515  if (EI.GetSrcNId() != EI.GetDstNId()) {
516  if (Alphas.IsKey(TIntPr(EI.GetSrcNId(), EI.GetDstNId())))
517  FOut.PutStr(TStr::Fmt("%d,%d,%f\r\n", EI.GetSrcNId(), EI.GetDstNId(), Alphas.GetDat(TIntPr(EI.GetSrcNId(), EI.GetDstNId())).Val));
518  else
519  FOut.PutStr(TStr::Fmt("%d,%d,1\r\n", EI.GetSrcNId(), EI.GetDstNId()));
520  }
521  }
522 }
523 
524 void TNetInfBs::SaveCascades(const TStr& OutFNm) {
525  TFOut FOut(OutFNm);
526 
527  // write nodes to file
528  for (TNGraph::TNodeI NI = GroundTruth->BegNI(); NI < GroundTruth->EndNI(); NI++) {
529  FOut.PutStr(TStr::Fmt("%d,%d\r\n", NI.GetId(), NI.GetId())); // nodes
530  }
531 
532  FOut.PutStr("\r\n");
533 
534  // write cascades to file
535  for (int i=0; i<CascV.Len(); i++) {
536  TCascade &C = CascV[i];
537  int j = 0;
538  for (THash<TInt, THitInfo>::TIter NI = C.NIdHitH.BegI(); NI < C.NIdHitH.EndI(); NI++, j++) {
539  if (j > 0)
540  FOut.PutStr(TStr::Fmt(",%d,%f", NI.GetDat().NId.Val, NI.GetDat().Tm.Val));
541  else
542  FOut.PutStr(TStr::Fmt("%d,%f", NI.GetDat().NId.Val, NI.GetDat().Tm.Val));
543  }
544 
545  if (C.Len() >= 1)
546  FOut.PutStr(TStr::Fmt("\r\n"));
547  }
548 }
TFlt MarginalGain
Definition: cascnetinf.h:65
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
void AddNodeNm(const int &NId, const TNodeInfo &Info)
Definition: cascnetinf.h:115
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TIntPrFltH Alphas
Definition: cascnetinf.h:94
TFlt Eps
Definition: cascnetinf.h:23
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
TFlt CurProb
Definition: cascnetinf.h:23
PNGraph Graph
Definition: cascnetinf.h:90
void SavePng(const int &SizeX=1000, const int &SizeY=800, const TStr &Comment=TStr())
Definition: gnuplot.h:120
int Val
Definition: dt.h:1139
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
TFlt MedianTimeDiff
Definition: cascnetinf.h:65
static double GetMx(const double &Flt1, const double &Flt2)
Definition: dt.h:1444
int Len() const
Definition: cascdynetinf.h:97
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:596
double GetProb(const PNGraph &G)
Definition: cascnetinf.cpp:17
void LoadCascadesTxt(TSIn &SIn, const int &Model, const double &alpha)
Definition: cascnetinf.cpp:62
TIter BegI() const
Definition: hash.h:213
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
double Val
Definition: dt.h:1388
int GetParent(const int NId) const
Definition: cascnetinf.h:36
Definition: fl.h:319
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
double TransProb(const int &NId1, const int &NId2) const
Definition: cascnetinf.cpp:4
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:594
TModel
Definition: cascdynetinf.h:7
double GetRayleigh(const double &Sigma)
Definition: dt.h:50
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
void SavePlaneTextNet(const TStr &OutFNm)
Definition: cascnetinf.cpp:455
THash< TInt, THitInfo > NIdHitH
Definition: cascdynetinf.h:87
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TIter EndI() const
Definition: hash.h:218
void SaveObjInfo(const TStr &OutFNm)
Definition: cascnetinf.cpp:485
static TRnd Rnd
Definition: dt.h:1146
double UpdateProb(const int &N1, const int &N2, const bool &UpdateProb=false)
Definition: cascnetinf.cpp:47
static const double Mx
Definition: dt.h:1391
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
const TKey & GetKey() const
Definition: hash.h:80
Definition: dt.h:1386
THash< TIntPr, TIntV > CascPerEdge
Definition: cascnetinf.h:89
Definition: fl.h:58
void SaveEdgeInfo(const TStr &OutFNm)
Definition: cascnetinf.cpp:470
void Init()
Definition: cascnetinf.cpp:216
TInt Model
Definition: cascdynetinf.h:88
bool CompareGroundTruth
Definition: cascnetinf.h:91
double GetTm(const int &NId) const
Definition: cascdynetinf.h:104
TFlt Alpha
Definition: cascnetinf.h:23
TVec< TPair< TFlt, TIntPr > > EdgeGainV
Definition: cascnetinf.h:87
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void GreedyOpt(const int &MxEdges)
Definition: cascnetinf.cpp:374
const TDat & GetDat() const
Definition: hash.h:81
double GetExpDev()
Definition: dt.cpp:83
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
virtual bool Eof()=0
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
void InitProb()
Definition: cascnetinf.cpp:40
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 graph.
Definition: graph.cpp:363
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:603
TInt Parent
Definition: cascnetinf.h:9
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
void SaveCascades(const TStr &OutFNm)
Definition: cascnetinf.cpp:524
void SavePajek(const TStr &OutFNm)
Definition: cascnetinf.cpp:439
THash< TIntPr, TEdgeInfo > EdgeInfoH
Definition: cascnetinf.h:86
void Clr()
Definition: cascdynetinf.h:95
TNodeInfo GetNodeInfo(const int &NId) const
Definition: cascnetinf.h:117
TFlt AverageTimeDiff
Definition: cascnetinf.h:65
void GenCascade(TCascade &C, const int &TModel, const double &window, TIntPrIntH &EdgesUsed, const double &delta, const double &std_waiting_time=0, const double &std_beta=0)
Definition: cascnetinf.cpp:113
Definition: dt.h:1137
PNGraph GroundTruth
Definition: cascnetinf.h:90
int Len() const
Definition: shash.h:1121
Definition: ds.h:32
TVec< TCascade > CascV
Definition: cascnetinf.h:84
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
void AddCasc(const TStr &CascStr, const int &Model=0, const double &alpha=1.0)
Definition: cascnetinf.cpp:98
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
Definition: dt.h:412
TIntPrFltH Betas
Definition: cascnetinf.h:94
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
void Add(const int &NId, const double &HitTm)
Definition: cascdynetinf.h:107
int PutStr(const char *CStr)
Definition: fl.cpp:117
void SplitOnAllCh(const char &SplitCh, TStrV &StrV, const bool &SkipEmpty=true) const
Definition: dt.cpp:926
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
double GetAllCascProb(const int &EdgeN1, const int &EdgeN2)
Definition: cascnetinf.cpp:255
TVal1 Val1
Definition: ds.h:34
int AddPlot(const TIntV &YValV, const TGpSeriesTy &SeriesTy=gpwLinesPoints, const TStr &Label=TStr(), const TStr &Style=TStr())
Definition: gnuplot.cpp:186
TVal2 Val2
Definition: ds.h:35
TVec< TInt > TIntV
Definition: ds.h:1594
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
void LoadGroundTruthTxt(TSIn &SIn)
Definition: cascnetinf.cpp:75
TInt Vol
Definition: cascnetinf.h:64
int GetNode(const int &i) const
Definition: cascdynetinf.h:100
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:404
char * CStr()
Definition: dt.h:479
bool IsKey(const TKey &Key) const
Definition: hash.h:258
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:412
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TFltPrV PrecisionRecall
Definition: cascnetinf.h:92
void Sort()
Definition: cascdynetinf.h:110
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
double GetBound(const TIntPr &Edge, double &CurProb)
Definition: cascnetinf.cpp:356
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
bool IsNode(const int &NId) const
Definition: cascdynetinf.h:109
double GetPowerDev(const double &AlphaSlope)
Definition: dt.h:47
void SaveGroundTruth(const TStr &OutFNm)
Definition: cascnetinf.cpp:502
static TRnd Rnd
Definition: dt.h:1396
static const double Mn
Definition: dt.h:1390
bool GetNextLn(TStr &LnStr)
Definition: fl.cpp:43
void SortByDat(const bool &Asc=true)
Definition: hash.h:292
TIntPr GetBestEdge(double &CurProb, double &LastGain, bool &msort, int &attempts)
Definition: cascnetinf.cpp:271