SNAP Library 3.0, Developer Reference  2016-07-20 17:56:49
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
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:479
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:1046
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:425
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
TFlt MedianTimeDiff
Definition: cascnetinf.h:65
static double GetMx(const double &Flt1, const double &Flt2)
Definition: dt.h:1351
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:516
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:171
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
double Val
Definition: dt.h:1295
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:547
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:514
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:438
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:220
TIter EndI() const
Definition: hash.h:176
void SaveObjInfo(const TStr &OutFNm)
Definition: cascnetinf.cpp:485
static TRnd Rnd
Definition: dt.h:1053
double UpdateProb(const int &N1, const int &N2, const bool &UpdateProb=false)
Definition: cascnetinf.cpp:47
static const double Mx
Definition: dt.h:1298
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
const TKey & GetKey() const
Definition: hash.h:71
Definition: dt.h:1293
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:971
void GreedyOpt(const int &MxEdges)
Definition: cascnetinf.cpp:374
const TDat & GetDat() const
Definition: hash.h:72
double GetExpDev()
Definition: dt.cpp:83
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:386
virtual bool Eof()=0
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs 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:807
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:523
TInt Parent
Definition: cascnetinf.h:9
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:477
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:1044
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:481
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:362
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:339
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:1529
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:319
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:360
char * CStr()
Definition: dt.h:476
bool IsKey(const TKey &Key) const
Definition: hash.h:216
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:368
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TFltPrV PrecisionRecall
Definition: cascnetinf.h:92
void Sort()
Definition: cascdynetinf.h:110
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
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:372
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:1303
static const double Mn
Definition: dt.h:1297
bool GetNextLn(TStr &LnStr)
Definition: fl.cpp:43
void SortByDat(const bool &Asc=true)
Definition: hash.h:250
TIntPr GetBestEdge(double &CurProb, double &LastGain, bool &msort, int &attempts)
Definition: cascnetinf.cpp:271