SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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
cascdynetinf.cpp
Go to the documentation of this file.
1 #include "stdafx.h"
2 #include "cascdynetinf.h"
3 
5  TStr Line;
6  while (!SIn.Eof()) {
7  SIn.GetNextLn(Line);
8  if (Line=="") { break; }
9  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
10  AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0));
11  }
12  printf("All nodes read!\n");
13  while (!SIn.Eof()) { SIn.GetNextLn(Line); AddCasc(Line, Model); }
14 
15  printf("All cascades read!\n");
16 }
17 
19  bool verbose = false;
20  TStr Line;
21 
22  Network.Clr(); // clear network (if any)
23 
24  // add nodes
25  while (!SIn.Eof()) {
26  SIn.GetNextLn(Line);
27  if (Line=="") { break; }
28  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
29  Network.AddNode(NIdV[0].GetInt(), NIdV[1]);
30  if (!IsNodeNm(NIdV[0].GetInt())) {
31  AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0));
32  DomainsIdH.AddDat(NIdV[1]) = NIdV[0].GetInt();
33  }
34  }
35 
36  // add edges
37  while (!SIn.Eof()) {
38  SIn.GetNextLn(Line);
39  TStrV FieldsV; Line.SplitOnAllCh(',', FieldsV);
40 
41  TFltFltH Alphas;
42  if (FieldsV.Len() == 3) {
43  Alphas.AddDat(0.0) = FieldsV[2].GetFlt();
44  } else {
45  for (int i=2; i<FieldsV.Len()-1; i+=2) {
46  Alphas.AddDat(FieldsV[i].GetFlt()) = FieldsV[i+1].GetFlt();
47  }
48  }
49 
50  Network.AddEdge(FieldsV[0].GetInt(), FieldsV[1].GetInt(), Alphas);
51 
52  if (verbose) {
53  printf("Edge %d -> %d: ", FieldsV[0].GetInt(), FieldsV[1].GetInt());
54  TFltFltH &AlphasE = Network.GetEDat(FieldsV[0].GetInt(), FieldsV[1].GetInt());
55  for (int i=0; i<AlphasE.Len(); i+=2) { printf("(%f, %f)", AlphasE.GetKey(i).Val, AlphasE[i].Val); }
56  printf("\n");
57  }
58  }
59 
60  printf("groundtruth nodes:%d edges:%d\n", Network.GetNodes(), Network.GetEdges());
61 }
62 
64  TStr Line;
65 
66  Network.Clr(); // clear network (if any)
67 
68  // add nodes
69  while (!SIn.Eof()) {
70  SIn.GetNextLn(Line);
71  if (Line=="") { break; }
72  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
73  Network.AddNode(NIdV[0].GetInt(), NIdV[1]);
74  if (!IsNodeNm(NIdV[0].GetInt())) {
75  AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0));
76  DomainsIdH.AddDat(NIdV[1]) = NIdV[0].GetInt();
77  }
78  }
79 
80  printf("groundtruth nodes:%d\n", Network.GetNodes());
81 }
82 
84  bool verbose = false;
85  TStr Line;
86 
87  InferredNetwork.Clr(); // clear network (if any)
88 
89  // add nodes
90  while (!SIn.Eof()) {
91  SIn.GetNextLn(Line);
92  if (Line=="") { break; }
93  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
94  if (DomainsIdH.IsKey(NIdV[1])) { IAssert(NIdV[0].GetInt()==DomainsIdH.GetDat(NIdV[1])); }
95  InferredNetwork.AddNode(NIdV[0].GetInt(), NIdV[1]);
96  if (!IsNodeNm(NIdV[0].GetInt())) { AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0)); }
97  if (!DomainsIdH.IsKey(NIdV[1])) { DomainsIdH.AddDat(NIdV[1]) = NIdV[0].GetInt(); }
98  if (verbose) { printf("Node:%s\n", NIdV[1].CStr()); }
99  }
100 
101  // add edges
102  while (!SIn.Eof()) {
103  SIn.GetNextLn(Line);
104  TStrV FieldsV; Line.SplitOnAllCh(',', FieldsV);
105 
106  TFltFltH Alphas;
107  if (FieldsV.Len() == 3) {
108  Alphas.AddDat(0.0) = FieldsV[2].GetFlt();
109  } else {
110  for (int i=2; i<FieldsV.Len()-1; i+=2) {
111  Alphas.AddDat(FieldsV[i].GetFlt()) = FieldsV[i+1].GetFlt();
112  }
113  }
114 
115  InferredNetwork.AddEdge(FieldsV[0].GetInt(), FieldsV[1].GetInt(), Alphas);
116 
117  if (verbose) {
118  printf("Edge %d -> %d: ", FieldsV[0].GetInt(), FieldsV[1].GetInt());
119  TFltFltH &AlphasE = InferredNetwork.GetEDat(FieldsV[0].GetInt(), FieldsV[1].GetInt());
120  for (int i=0; i<AlphasE.Len(); i+=2) { printf("(%f, %f)", AlphasE.GetKey(i).Val, AlphasE[i].Val); }
121  printf("\n");
122  }
123  }
124 
125  printf("inferred nodes:%d edges:%d\n", InferredNetwork.GetNodes(), InferredNetwork.GetEdges());
126 }
127 
129  TStr Line;
130 
131  InferredNetwork.Clr(); // clear network (if any)
132 
133  // add nodes
134  while (!SIn.Eof()) {
135  SIn.GetNextLn(Line);
136  if (Line=="") { break; }
137  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
138  if (DomainsIdH.IsKey(NIdV[1])) { IAssert(NIdV[0].GetInt()==DomainsIdH.GetDat(NIdV[1])); }
139  InferredNetwork.AddNode(NIdV[0].GetInt(), NIdV[1]);
140  if (!IsNodeNm(NIdV[0].GetInt())) { AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0)); }
141  if (!DomainsIdH.IsKey(NIdV[1])) { DomainsIdH.AddDat(NIdV[1]) = NIdV[0].GetInt(); }
142  }
143 
144  printf("Nodes:%d\n", InferredNetwork.GetNodes());
145 }
146 
147 void TNIBs::AddCasc(const TStr& CascStr, const TModel& Model) {
148  int CId = CascH.Len();
149 
150  // support cascade id if any
151  TStrV FieldsV; CascStr.SplitOnAllCh(';', FieldsV);
152  if (FieldsV.Len()==2) { CId = FieldsV[0].GetInt(); }
153 
154  // read nodes
155  TStrV NIdV; FieldsV[FieldsV.Len()-1].SplitOnAllCh(',', NIdV);
156  TCascade C(CId, Model);
157  for (int i = 0; i < NIdV.Len(); i+=2) {
158  int NId;
159  double Tm;
160  NId = NIdV[i].GetInt();
161  Tm = NIdV[i+1].GetFlt();
162  GetNodeInfo(NId).Vol = GetNodeInfo(NId).Vol + 1;
163  C.Add(NId, Tm);
164  }
165  C.Sort();
166 
167  AddCasc(C);
168 }
169 
170 void TNIBs::AddCasc(const TIntFltH& Cascade, const int& CId, const TModel& Model) {
171  TCascade C(CId, Model);
172  for (TIntFltH::TIter NI = Cascade.BegI(); NI < Cascade.EndI(); NI++) {
173  GetNodeInfo(NI.GetKey()).Vol = GetNodeInfo(NI.GetKey()).Vol + 1;
174  C.Add(NI.GetKey(), NI.GetDat());
175  }
176  C.Sort();
177  AddCasc(C);
178 }
179 
181  bool verbose = false;
182  TIntFltH InfectedNIdH; TIntH InfectedBy;
183  double GlobalTime, InitTime;
184  double alpha;
185  int StartNId;
186 
187  if (Network.GetNodes() == 0)
188  return;
189 
190  // set random seed
192 
193  while (C.Len() < 2) {
194  C.Clr();
195  InfectedNIdH.Clr();
196  InfectedBy.Clr();
197 
198  InitTime = TFlt::Rnd.GetUniDev() * TotalTime; // random starting point <TotalTime
199  GlobalTime = InitTime;
200 
201  StartNId = Network.GetRndNId();
202  InfectedNIdH.AddDat(StartNId) = GlobalTime;
203 
204  while (true) {
205  // sort by time & get the oldest node that did not run infection
206  InfectedNIdH.SortByDat(true);
207  const int& NId = InfectedNIdH.BegI().GetKey();
208  GlobalTime = InfectedNIdH.BegI().GetDat();
209 
210  // all the nodes has run infection
211  if ( GlobalTime >= TFlt::GetMn(TotalTime, InitTime+Window) )
212  break;
213 
214  // add current oldest node to the network and set its time
215  C.Add(NId, GlobalTime);
216 
217  if (verbose) { printf("GlobalTime:%f, infected node:%d\n", GlobalTime, NId); }
218 
219  // run infection from the current oldest node
220  TStrFltFltHNEDNet::TNodeI NI = Network.GetNI(NId);
221  for (int e = 0; e < NI.GetOutDeg(); e++) {
222  const int DstNId = NI.GetOutNId(e);
223 
224  // choose the current tx rate (we assume the most recent tx rate)
225  TFltFltH& Alphas = Network.GetEDat(NId, DstNId);
226  for (int j=0; j<Alphas.Len() && Alphas.GetKey(j)<GlobalTime; j++) { alpha = Alphas[j]; }
227  if (verbose) { printf("GlobalTime:%f, nodes:%d->%d, alpha:%f\n", GlobalTime, NId, DstNId, alpha); }
228 
229  if (alpha<1e-9) { continue; }
230 
231  // not infecting the parent
232  if (InfectedBy.IsKey(NId) && InfectedBy.GetDat(NId).Val == DstNId)
233  continue;
234 
235  double sigmaT;
236  switch (Model) {
237  case EXP:
238  // exponential with alpha parameter
239  sigmaT = TInt::Rnd.GetExpDev(alpha);
240  break;
241  case POW:
242  // power-law with alpha parameter
243  sigmaT = TInt::Rnd.GetPowerDev(1+alpha);
244  while (sigmaT < Delta) { sigmaT = Delta*TInt::Rnd.GetPowerDev(1+alpha); }
245  break;
246  case RAY:
247  // rayleigh with alpha parameter
248  sigmaT = TInt::Rnd.GetRayleigh(1/sqrt(alpha));
249  break;
250  default:
251  sigmaT = 1;
252  break;
253  }
254 
255  IAssert(sigmaT >= 0);
256 
257  double t1 = TFlt::GetMn(GlobalTime + sigmaT, TFlt::GetMn(InitTime+Window, TotalTime));
258 
259  if (InfectedNIdH.IsKey(DstNId)) {
260  double t2 = InfectedNIdH.GetDat(DstNId);
261  if ( t2 > t1 && t2 < TFlt::GetMn(InitTime+Window, TotalTime)) {
262  InfectedNIdH.GetDat(DstNId) = t1;
263  InfectedBy.GetDat(DstNId) = NId;
264  }
265  } else {
266  InfectedNIdH.AddDat(DstNId) = t1;
267  InfectedBy.AddDat(DstNId) = NId;
268  }
269  }
270 
271  // we cannot delete key (otherwise, we cannot sort), so we assign a big time (InitTime + window cut-off)
272  InfectedNIdH.GetDat(NId) = TFlt::GetMn(InitTime+Window, TotalTime);
273  }
274  }
275 
276  C.Sort();
277 }
278 
279 void TNIBs::GetGroundTruthGraphAtT(const double& Step, PNGraph &GraphAtT) {
280  GraphAtT = TNGraph::New();
281 
282  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) { GraphAtT->AddNode(NI.GetKey()); }
283 
284  for (TStrFltFltHNEDNet::TEdgeI EI = Network.BegEI(); EI < Network.EndEI(); EI++) {
285  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
286  double Alpha = 0.0;
287  if (EI().IsKey(Step)) { Alpha = EI().GetDat(Step); }
288 
289  if (Alpha > MinAlpha) {
290  GraphAtT->AddEdge(EI.GetSrcNId(), EI.GetDstNId());
291  }
292  }
293 }
294 
295 void TNIBs::GetGroundTruthNetworkAtT(const double& Step, PStrFltNEDNet& NetworkAtT) {
296  NetworkAtT = TStrFltNEDNet::New();
297 
298  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) { NetworkAtT->AddNode(NI.GetKey(), NI.GetDat().Name); }
299 
300  for (TStrFltFltHNEDNet::TEdgeI EI = Network.BegEI(); EI < Network.EndEI(); EI++) {
301  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
302  double Alpha = 0.0;
303  if (EI().IsKey(Step)) { Alpha = EI().GetDat(Step); }
304 
305  if (Alpha > MinAlpha) {
306  NetworkAtT->AddEdge(EI.GetSrcNId(), EI.GetDstNId(), Alpha);
307  }
308  }
309 }
310 
311 void TNIBs::GetInferredGraphAtT(const double& Step, PNGraph &GraphAtT) {
312  GraphAtT = TNGraph::New();
313 
314  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) { GraphAtT->AddNode(NI.GetKey()); }
315 
316  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
317  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
318 
319  double inferredAlpha = 0.0;
320  if (EI().IsKey(Step)) { inferredAlpha = EI().GetDat(Step); }
321 
322  if (inferredAlpha > MinAlpha) {
323  GraphAtT->AddEdge(EI.GetSrcNId(), EI.GetDstNId());
324  }
325  }
326 }
327 
328 void TNIBs::GetInferredNetworkAtT(const double& Step, PStrFltNEDNet& NetworkAtT) {
329  NetworkAtT = TStrFltNEDNet::New();
330 
331  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
332  NetworkAtT->AddNode(NI.GetKey(), NI.GetDat().Name);
333  }
334 
335  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
336  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
337 
338  double inferredAlpha = 0.0;
339  if (EI().IsKey(Step)) { inferredAlpha = EI().GetDat(Step); }
340 
341  if (inferredAlpha > MinAlpha) {
342  NetworkAtT->AddEdge(EI.GetSrcNId(), EI.GetDstNId(), inferredAlpha);
343  }
344  }
345 }
346 
347 void TNIBs::Init(const TFltV& Steps) {
348  // inferred network
350 
351  // copy nodes from NodeNmH (it will be filled by loading cascades or loading groundtruth)
352  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
353  InferredNetwork.AddNode(NI.GetKey(), NI.GetDat().Name);
354  }
355 
356  // performance measures
358  Accuracy.Clr();
359  MAE.Clr();
361 
362  for (int i=0; i<Steps.Len()-1; i++) {
363  MAE.Add(TFltPr(Steps[i], 0.0));
364  MSE.Add(TFltPr(Steps[i], 0.0));
365  Accuracy.Add(TFltPr(Steps[i], 0.0));
366  PrecisionRecall.Add(TFltPr(0.0,0.0));
367  }
368 }
369 
370 void TNIBs::Reset() {
371  // reset vectors
372  for (int i=0; i<DiffAlphas.Len(); i++) {
373  DiffAlphas[i].Clr();
374  }
375  DiffAlphas.Clr();
376  AveDiffAlphas.Clr();
379 }
380 
381 void TNIBs::SG(const int& NId, const int& Iters, const TFltV& Steps, const TSampling& Sampling, const TStr& ParamSampling, const bool& PlotPerformance) {
382  bool verbose = false;
383  int currentCascade = -1;
384  TIntIntH SampledCascades;
385  TStrV ParamSamplingV; ParamSampling.SplitOnAllCh(';', ParamSamplingV);
386 
387  Reset();
388 
389  printf("Node %d\n", NId);
390 
391  // traverse through all times
392  for (int t=1; t<Steps.Len(); t++) {
393  // find cascades whose two first infections are earlier than Steps[t]
394  TIntFltH CascadesIdx;
395  int num_infections = 0;
396  for (int i=0; i<CascH.Len(); i++) {
397  if (CascH[i].LenBeforeT(Steps[t]) > 1 &&
398  ( (Sampling!=WIN_SAMPLING && Sampling!=WIN_EXP_SAMPLING) ||
399  (Sampling==WIN_SAMPLING && (Steps[t]-CascH[i].GetMinTm()) <= ParamSamplingV[0].GetFlt()) ||
400  (Sampling==WIN_EXP_SAMPLING && (Steps[t]-CascH[i].GetMinTm()) <= ParamSamplingV[0].GetFlt()) )) {
401  num_infections += CascH[i].LenBeforeT(Steps[t]);
402  CascadesIdx.AddDat(i) = CascH[i].GetMinTm();
403  }
404  }
405 
406  // if there are not recorded cascades by Steps[t], continue
407  if (CascadesIdx.Len()==0) {
408  printf("WARNING: No cascades recorded by %f!\n", Steps[t].Val);
409  if (PlotPerformance) { ComputePerformanceNId(NId, t, Steps); }
410  continue;
411  }
412 
413  // later cascades first
414  CascadesIdx.SortByDat(false);
415 
416  printf("Solving step %f: %d cascades, %d infections\n", Steps[t].Val, CascadesIdx.Len(), num_infections);
417  SampledCascades.Clr();
418 
419  // sampling cascades with no replacement
420  for (int i=0; i < Iters; i++) {
421  switch (Sampling) {
422  case UNIF_SAMPLING:
423  currentCascade = TInt::Rnd.GetUniDevInt(CascadesIdx.Len());
424  break;
425 
426  case WIN_SAMPLING:
427  currentCascade = TInt::Rnd.GetUniDevInt(CascadesIdx.Len());
428  break;
429 
430  case EXP_SAMPLING:
431  do {
432  currentCascade = (int)TFlt::Rnd.GetExpDev(ParamSamplingV[0].GetFlt());
433  } while (currentCascade > CascadesIdx.Len()-1);
434  break;
435 
436  case WIN_EXP_SAMPLING:
437  do {
438  currentCascade = (int)TFlt::Rnd.GetExpDev(ParamSamplingV[1].GetFlt());
439  } while (currentCascade > CascadesIdx.Len()-1);
440  break;
441 
442  case RAY_SAMPLING:
443  do {
444  currentCascade = (int)TFlt::Rnd.GetRayleigh(ParamSamplingV[0].GetFlt());
445  } while (currentCascade > CascadesIdx.Len()-1);
446  break;
447  }
448 
449  if (!SampledCascades.IsKey(currentCascade)) { SampledCascades.AddDat(currentCascade) = 0; }
450  SampledCascades.GetDat(currentCascade)++;
451 
452  if (verbose) { printf("Cascade %d sampled!\n", currentCascade); }
453 
454  // sampled cascade
455  TCascade &Cascade = CascH[CascadesIdx.GetKey(currentCascade)];
456 
457  // update gradient and alpha's
458  TIntPrV AlphasToUpdate;
459  UpdateDiff(OSG, NId, Cascade, AlphasToUpdate, Steps[t]);
460 
461  // update alpha's
462  for (int j=0; j<AlphasToUpdate.Len(); j++) {
463  if (InferredNetwork.IsEdge(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2) &&
464  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).IsKey(Steps[t])
465  ) {
466  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) -=
467  (Gamma * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1)
468  - (Regularizer==1? Mu*InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) : 0.0));
469 
470  // project into alpha >= 0
471  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) < Tol) {
472  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = Tol;
473  }
474 
475  // project into alpha <= MaxAlpha
476  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) > MaxAlpha) {
477  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = MaxAlpha;
478  }
479  }
480  }
481  if (verbose) { printf("%d transmission rates updated!\n", AlphasToUpdate.Len()); }
482  }
483 
484  printf("%d different cascades have been sampled for step %f!\n", SampledCascades.Len(), Steps[t].Val);
485 
486  // For alphas that did not get updated, copy last alpha value * aging factor
487  int unchanged = 0;
488  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
489  if (EI().IsKey(Steps[t]) || t == 0 || !EI().IsKey(Steps[t-1])) { continue; }
490 
491  EI().AddDat(Steps[t]) = Aging*EI().GetDat(Steps[t-1]);
492  unchanged++;
493  }
494  if (verbose) { printf("%d transmission rates that did not changed were 'aged' by %f!\n", unchanged, Aging.Val); }
495 
496  // compute performance on-the-fly
497  if (PlotPerformance) { ComputePerformanceNId(NId, t, Steps); }
498  }
499 }
500 
501 void TNIBs::BSG(const int& NId, const int& Iters, const TFltV& Steps, const int& BatchLen, const TSampling& Sampling, const TStr& ParamSampling, const bool& PlotPerformance) {
502  bool verbose = false;
503  int currentCascade = -1;
504  TIntIntH SampledCascades;
505  TStrV ParamSamplingV; ParamSampling.SplitOnAllCh(';', ParamSamplingV);
506 
507  Reset();
508 
509  printf("Node %d (|A|: %d)\n", NId, InferredNetwork.GetNodes());
510 
511  // traverse through all times (except 0.0; we use 0.0 to compute mse/mae since the inference is delayed)
512  for (int t=1; t<Steps.Len(); t++) {
513  // find cascades whose two first infections are earlier than Steps[t]
514  TIntFltH CascadesIdx;
515  int num_infections = 0;
516  for (int i = 0; i < CascH.Len(); i++) {
517  if (CascH[i].LenBeforeT(Steps[t]) > 1 &&
518  ( (Sampling!=WIN_SAMPLING && Sampling!=WIN_EXP_SAMPLING) ||
519  (Sampling==WIN_SAMPLING && (Steps[t]-CascH[i].GetMinTm()) <= ParamSamplingV[0].GetFlt()) ||
520  (Sampling==WIN_EXP_SAMPLING && (Steps[t]-CascH[i].GetMinTm()) <= ParamSamplingV[0].GetFlt()) )) {
521  num_infections += CascH[i].LenBeforeT(Steps[t]);
522  CascadesIdx.AddDat(i) = CascH[i].GetMinTm();
523  }
524  }
525 
526  // if there are not recorded cascades by Steps[t], continue
527  if (CascadesIdx.Len() == 0) {
528  printf("WARNING: No cascades recorded by %f!\n", Steps[t].Val);
529  if (PlotPerformance) { ComputePerformanceNId(NId, t, Steps); }
530  continue;
531  }
532 
533  printf("Solving step %f (%d cascades, %d infections)\n", Steps[t].Val,
534  CascadesIdx.Len(), num_infections);
535 
536  // sort cascade from most recent to least recent
537  CascadesIdx.SortByDat(false);
538 
539  // sampling cascades with no replacement
540  for (int i=0; i < Iters; i++) {
541  // alphas to update
542  TIntPrV AlphasToUpdate;
543 
544  // delete average gradients
545  AveDiffAlphas.Clr();
546 
547  // use all cascades for the average gradient
548  for (int c=0; c<BatchLen; c++) {
549  switch (Sampling) {
550  case UNIF_SAMPLING:
551  currentCascade = TInt::Rnd.GetUniDevInt(CascadesIdx.Len());
552  break;
553 
554  case WIN_SAMPLING:
555  currentCascade = TInt::Rnd.GetUniDevInt(CascadesIdx.Len());
556  break;
557 
558  case EXP_SAMPLING:
559  do {
560  currentCascade = (int)TFlt::Rnd.GetExpDev(ParamSamplingV[0].GetFlt());
561  } while (currentCascade > CascadesIdx.Len()-1);
562  break;
563 
564  case WIN_EXP_SAMPLING:
565  do {
566  currentCascade = (int)TFlt::Rnd.GetExpDev(ParamSamplingV[1].GetFlt());
567  } while (currentCascade > CascadesIdx.Len()-1);
568  break;
569 
570  case RAY_SAMPLING:
571  do {
572  currentCascade = (int)TFlt::Rnd.GetRayleigh(ParamSamplingV[0].GetFlt());
573  } while (currentCascade > CascadesIdx.Len()-1);
574  break;
575  }
576 
577  // sampled cascade
578  TCascade &Cascade = CascH[CascadesIdx.GetKey(currentCascade)];
579 
580  if (!SampledCascades.IsKey(currentCascade)) { SampledCascades.AddDat(currentCascade) = 0; }
581  SampledCascades.GetDat(currentCascade)++;
582 
583  // update gradient and alpha's
584  UpdateDiff(OBSG, NId, Cascade, AlphasToUpdate, Steps[t]);
585  }
586 
587  // update alpha's
588  for (int j=0; j<AlphasToUpdate.Len(); j++) {
589  if (InferredNetwork.IsEdge(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2) &&
590  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).IsKey(Steps[t])) {
591  switch (Regularizer) {
592  case 0:
593  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) -=
594  Gamma * (1.0/(double)BatchLen) * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1);
595  case 1:
596  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) =
597  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t])*(1.0-Mu*Gamma/(double)BatchLen)
598  - Gamma * (1.0/(double)BatchLen) * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1);
599  }
600 
601  // project into alpha >= 0
602  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) < Tol) {
603  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = Tol;
604  }
605 
606  // project into alpha <= MaxAlpha
607  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) > MaxAlpha) {
608  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = MaxAlpha;
609  }
610  }
611  }
612 
613  // for alphas that did not get updated, copy last alpha value
614  int unchanged = 0;
615  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
616  if (EI().IsKey(Steps[t]) || t == 0 || !EI().IsKey(Steps[t-1])) { continue; }
617 
618  EI().AddDat(Steps[t]) = EI().GetDat(Steps[t-1]);
619  unchanged++;
620  }
621  if (verbose) { printf("%d unchanged transmission rates updated!\n", unchanged); }
622  }
623 
624  printf("%d different cascades have been sampled for step %f!\n", SampledCascades.Len(), Steps[t].Val);
625 
626  // compute performance on-the-fly for each time step
627  if (PlotPerformance) { ComputePerformanceNId(NId, t, Steps); }
628  }
629 }
630 
631 void TNIBs::FG(const int& NId, const int& Iters, const TFltV& Steps) {
632  bool verbose = false;
633 
634  Reset();
635 
636  printf("Node %d (|A|: %d)\n", NId, InferredNetwork.GetNodes());
637 
638  // traverse through all times
639  for (int t=1; t<Steps.Len(); t++) {
640  // find cascades whose two first infections are earlier than Steps[t]
641  TIntFltH CascadesIdx;
642  int num_infections = 0;
643  for (int i=0; i<CascH.Len(); i++) {
644  if (CascH[i].LenBeforeT(Steps[t]) > 1) {
645  num_infections += CascH[i].LenBeforeT(Steps[t]);
646  CascadesIdx.AddDat(i) = CascH[i].GetMinTm();
647  }
648  }
649 
650  // if there are not recorded cascades by Steps[t], continue
651  if (CascadesIdx.Len()==0) {
652  printf("WARNING: No cascades recorded by %f!\n", Steps[t].Val);
653 // ComputePerformance(NId, Tol, t, Steps);
654  continue;
655  }
656 
657  printf("Solving step %f (%d cascades, %d infections)\n", Steps[t].Val, CascadesIdx.Len(), num_infections);
658 
659  // sort cascade from most recent to least recent
660  CascadesIdx.SortByDat(false);
661 
662  // sampling cascades with no replacement
663  for (int i=0; i < Iters; i++) {
664  // alphas to update
665  TIntPrV AlphasToUpdate;
666 
667  // delete average gradients
668  AveDiffAlphas.Clr();
669 
670  // use all cascades for the average gradient
671  for (int c=0; c<CascadesIdx.Len(); c++) {
672  // each cascade
673  TCascade &Cascade = CascH[CascadesIdx.GetKey(c)];
674 
675  // update gradient and alpha's
676  UpdateDiff(OBSG, NId, Cascade, AlphasToUpdate, Steps[t]);
677  }
678 
679  // update alpha's
680  for (int j=0; j<AlphasToUpdate.Len(); j++) {
681  if (InferredNetwork.IsEdge(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2) &&
682  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).IsKey(Steps[t])) {
683  switch (Regularizer) {
684  case 0:
685  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) -=
686  Gamma * (1.0/(double)CascadesIdx.Len()) * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1);
687  case 1:
688  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) =
689  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t])*(1.0-Mu*Gamma/(double)CascadesIdx.Len())
690  - Gamma * (1.0/(double)CascadesIdx.Len()) * AveDiffAlphas.GetDat(AlphasToUpdate[j].Val1);
691  }
692 
693  // project into alpha >= 0
694  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) < Tol) {
695  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = Tol;
696  }
697 
698  // project into alpha <= MaxAlpha
699  if (InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) > MaxAlpha) {
700  InferredNetwork.GetEDat(AlphasToUpdate[j].Val1, AlphasToUpdate[j].Val2).GetDat(Steps[t]) = MaxAlpha;
701  }
702  }
703  }
704 
705  // for alphas that did not get updated, copy last alpha value
706  int unchanged = 0;
707  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
708  if (EI().IsKey(Steps[t]) || t == 0 || !EI().IsKey(Steps[t-1])) { continue; }
709 
710  EI().AddDat(Steps[t]) = EI().GetDat(Steps[t-1]);
711  unchanged++;
712  }
713  if (verbose) { printf("%d unchanged transmission rates updated!\n", unchanged); }
714  }
715 
716  // compute performance on-the-fly for each time step
717  ComputePerformanceNId(NId, t, Steps);
718  }
719 }
720 
721 void TNIBs::UpdateDiff(const TOptMethod& OptMethod, const int& NId, TCascade& Cascade, TIntPrV& AlphasToUpdate, const double& CurrentTime) {
723 
724  double sum = 0.0;
725 
726  // we assume cascade is sorted & iterator returns in sorted order
727  if (Cascade.IsNode(NId) && Cascade.GetTm(NId) <= CurrentTime) {
728  for (THash<TInt, THitInfo>::TIter NI = Cascade.BegI(); NI < Cascade.EndI(); NI++) {
729  // consider only nodes that are earlier in time
730  if ( (Cascade.GetTm(NId)<=NI.GetDat().Tm) ||
731  (Cascade.GetTm(NId)-Delta<=NI.GetDat().Tm && Model==POW)
732  ) { break; }
733 
734  TIntPr Pair(NI.GetKey(), NId);
735 
736  // if edge/alpha doesn't exist, create
737  if (!InferredNetwork.IsEdge(Pair.Val1, Pair.Val2)) { InferredNetwork.AddEdge(Pair.Val1, Pair.Val2, TFltFltH()); }
738  if (!InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).IsKey(CurrentTime)) {
739  InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).AddDat(CurrentTime) = InitAlpha;
740  }
741 
742  switch(Model) {
743  case EXP: // exponential
744  sum += InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).GetDat(CurrentTime).Val;
745  break;
746  case POW: // powerlaw
747  sum += InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).GetDat(CurrentTime).Val/(Cascade.GetTm(NId)-NI.GetDat().Tm);
748  break;
749  case RAY: // rayleigh
750  sum += InferredNetwork.GetEDat(Pair.Val1, Pair.Val2).GetDat(CurrentTime).Val*(Cascade.GetTm(NId)-NI.GetDat().Tm);
751  break;
752  default:
753  sum = 0.0;
754  }
755  }
756  }
757 
758  // we assume cascade is sorted & iterator returns in sorted order
759  for (THash<TInt, THitInfo>::TIter NI = Cascade.BegI(); NI < Cascade.EndI(); NI++) {
760  // only consider nodes that are earlier in time if node belongs to the cascade
761  if ( Cascade.IsNode(NId) && (Cascade.GetTm(NId)<=NI.GetDat().Tm ||
762  (Cascade.GetTm(NId)-Delta<=NI.GetDat().Tm && Model==POW))
763  ) { break; }
764 
765  // consider infected nodes up to CurrentTime
766  if (NI.GetDat().Tm > CurrentTime) { break; }
767 
768  TIntPr Pair(NI.GetKey(), NId); // potential edge
769 
770  double val = 0.0;
771 
772  if (Cascade.IsNode(NId) && Cascade.GetTm(NId) <= CurrentTime) {
773  IAssert((Cascade.GetTm(NId) - NI.GetDat().Tm) > 0.0);
774 
775  switch(Model) { // compute gradients for infected
776  case EXP: // exponential
777  val = (Cascade.GetTm(NId) - NI.GetDat().Tm) - 1.0/sum;
778  break;
779  case POW: // powerlaw
780  val = log((Cascade.GetTm(NId) - NI.GetDat().Tm)/Delta) - 1.0/((Cascade.GetTm(NId)-NI.GetDat().Tm)*sum);
781  break;
782  case RAY: // rayleigh
783  val = TMath::Power(Cascade.GetTm(NId)-NI.GetDat().Tm, 2.0)/2.0 - (Cascade.GetTm(NId)-NI.GetDat().Tm)/sum;
784  break;
785  default:
786  val = 0.0;
787  }
788  } else { // compute gradients for non infected
789  IAssert((CurrentTime - NI.GetDat().Tm) >= 0.0);
790 
791  switch(Model) {
792  case EXP: // exponential
793  val = (CurrentTime-NI.GetDat().Tm);
794  // if every cascade was recorded up to a maximum Window cut-off
795  if ( (Window > -1) && (CurrentTime-Cascade.GetMinTm() > Window) ) { val = (Cascade.GetMinTm()+Window-NI.GetDat().Tm); }
796  break;
797  case POW: // power-law
798  val = TMath::Mx(log((CurrentTime-NI.GetDat().Tm)/Delta), 0.0);
799  // if every cascade was recorded up to a maximum Window cut-off
800  if ( (Window > -1) && (CurrentTime-Cascade.GetMinTm() > Window) ) { val = TMath::Mx(log((Cascade.GetMinTm()+Window-NI.GetDat().Tm)/Delta), 0.0); }
801  break;
802  case RAY: // rayleigh
803  val = TMath::Power(CurrentTime-NI.GetDat().Tm,2.0)/2.0;
804  // if every cascade was recorded up to a maximum Window cut-off
805  if ( (Window > -1) && (CurrentTime-Cascade.GetMinTm() > Window) ) { val = TMath::Power(Cascade.GetMinTm()+Window-NI.GetDat().Tm,2.0)/2.0; }
806  break;
807  default:
808  val = 0.0;
809  }
810  }
811 
812  if (!AveDiffAlphas.IsKey(Pair.Val1)) { AveDiffAlphas.AddDat(Pair.Val1) = 0.0; }
813 
814  switch (OptMethod) {
815  case OBSG:
816  case OEBSG:
817  case OFG:
818  // update stochastic average gradient (based on batch for OBSG and OEBSG and based on all cascades for FG)
819  AveDiffAlphas.GetDat(Pair.Val1) += val;
820  break;
821  case OSG:
822  case OESG:
823  // update stochastic gradient (we use a single gradient due to current cascade)
824  AveDiffAlphas.GetDat(Pair.Val1) = val;
825  default:
826  break;
827  }
828 
829  AlphasToUpdate.Add(Pair);
830  }
831 
832  return;
833 }
834 
835 void TNIBs::find_C( int t, TFltV &x, TFltVV &C, const int& k, const double& s, const double& gamma, const double& T ){
836  if ( t >= x.Len() ) return;
837  if ( t == 0 ){
838  C = TFltVV( x.Len(), k );
839  }else{
840  int n = x.Len() - 1;
841  for (int j = 0; j < k; j++){
842  double alpha = ( (x.Len() ) / T ) * pow( s, j );
843  double term_1 = -log(alpha) + alpha * x[t];
844  double term_2 = 0;
845  if ( t == 1 ){
846  term_2 = j * log((double) n) * gamma;
847  }
848  else{
849  bool first = false;
850  for (int l = 0; l < k; l++){
851  double my_val = C(t-1, l);
852  if ( j > l ) my_val += (j - l) * log((double) n) * gamma;
853  if ( !first || my_val < term_2 ){
854  term_2 = my_val;
855  first = true;
856  }
857  }
858  }
859  C( t, j ) = term_1 + term_2;
860  }
861  }
862  find_C( t + 1, x, C, k, s, gamma, T );
863 }
864 
865 void TNIBs::find_min_state( TFltVV &C, TIntV &states, const int& k, const double& s, const double& gamma, const double& T ){
866  states = TIntV( C.GetRows() );
867  states[0] = 0;
868  int n = C.GetRows() - 1;
869  for (int t = C.GetRows() - 1; t > 0; t --){
870  double best_val = 0;
871  int best_state = -1;
872  for (int j = 0; j < C.GetCols(); j++){
873  double c_state = C( t, j );
874  if ( t < C.GetRows() - 2 && states[t+1] > j ){
875  c_state += ( states[t+1] - j ) * gamma * log((double) n);
876  }
877  if ( best_state == -1 || best_val > c_state ){
878  best_state = j;
879  best_val = c_state;
880  }
881  }
882  states[t] = best_state;
883  }
884 }
885 
886 void TNIBs::LabelBurstAutomaton( const int& SrcId, const int& DstId, TIntV &state_labels, TFltV &state_times, const bool& inferred, const int& k, const double& s, const double& gamma, const TSecTm& MinTime, const TSecTm& MaxTime ){
887  TVec<TSecTm> arrival_times;
888  TFltFltH &LinksEdge = (inferred? InferredNetwork.GetEDat(SrcId, DstId) : Network.GetEDat(SrcId, DstId));
889 
890  for (int i=0; i<LinksEdge.Len(); i++) {
891  if (LinksEdge[i]>MinAlpha) {
892  TSecTm tsecs;
893  tsecs = (uint)LinksEdge.GetKey(i); // link rates is in seconds
894  if (tsecs > MaxTime || tsecs < MinTime) { continue; }
895  arrival_times.Add(tsecs);
896  }
897  }
898 
899  if ( arrival_times.Len() < 2 ) return;
900 
901  TFltV x;
902  x.Add( 0 );
903  arrival_times.Sort(true);
904  double T = ((double)arrival_times.Last().GetAbsSecs()) - ((double)arrival_times[0].GetAbsSecs());
905  for (int i = 1; i < arrival_times.Len(); i++){
906  x.Add( ((double)arrival_times[i].GetAbsSecs()) - ((double)arrival_times[i-1].GetAbsSecs()) );
907  }
908  TFltVV Cost_matrix;
909  //printf("arrivals = %d\n", x.Len() );
910  find_C( 0, x, Cost_matrix, k, s, gamma, T);
911 
912  find_min_state( Cost_matrix, state_labels, k, s, gamma, T );
913 
914  for (int i=0; i<state_labels.Len(); i++) { state_times.Add((double)arrival_times[i].GetAbsSecs()); }
915 }
916 
917 
918 void TNIBs::ComputePerformanceNId(const int& NId, const int& t, const TFltV& Steps) {
919  double CurrentMAE = 0.0;
920  double CurrentMSE = 0.0;
921  TFltPr CurrentPrecisionRecall(0.0, 0.0);
922  double CurrentAccD = 0.0;
923 
924  TStrFltFltHNEDNet::TNodeI NI = InferredNetwork.GetNI(NId);
925  for (int i=0; i<NI.GetInDeg(); i++) {
926  double inferredAlpha = InferredNetwork.GetEDat(NI.GetInNId(i), NId).GetDat(Steps[t]);
927  // we get the true alpha in the previous step (the inferred network contains delayed estimates)
928  double trueAlpha = 0.0;
929  if (Network.IsEdge(NI.GetInNId(i), NId) && Network.GetEDat(NI.GetInNId(i), NId).IsKey(Steps[t-1])) { trueAlpha = Network.GetEDat(NI.GetInNId(i), NId).GetDat(Steps[t-1]); }
930 
931  // accuracy (denominator)
932  CurrentAccD += (double) (inferredAlpha > MinAlpha);
933 
934  // precision
935  CurrentPrecisionRecall.Val2 += (double) (inferredAlpha > MinAlpha && trueAlpha<MinAlpha);
936  }
937 
938  NI = Network.GetNI(NId);
939  int NumEdges = 0;
940  for (int i=0; i<NI.GetInDeg(); i++) {
941  TIntPr Pair(NI.GetInNId(i), NId);
942 
943  // we get the inferred Alpha if any
944  double inferredAlpha = 0.0;
945  if (InferredNetwork.IsEdge(NI.GetInNId(i), NId) && InferredNetwork.GetEDat(NI.GetInNId(i), NId).IsKey(Steps[t])) {
946  inferredAlpha = InferredNetwork.GetEDat(NI.GetInNId(i), NId).GetDat(Steps[t]).Val;
947  }
948 
949  // we get the true alpha in the previous step (the inferred network contains delayed estimates)
950  double trueAlpha = 0.0;
951  if (Network.GetEDat(NI.GetInNId(i), NId).IsKey(Steps[t-1])) { trueAlpha = Network.GetEDat(NI.GetInNId(i), NId).GetDat(Steps[t-1]); }
952 
953  // mae
954  if (trueAlpha > MinAlpha) {
955  NumEdges++;
956  CurrentMAE += fabs(trueAlpha - TFlt::GetMn(inferredAlpha, MaxAlpha))/trueAlpha;
957  }
958 
959  // mse
960  CurrentMSE += pow(trueAlpha - TFlt::GetMn(inferredAlpha, MaxAlpha), 2.0);
961 
962  // recall
963  CurrentPrecisionRecall.Val1 += (double) (inferredAlpha > MinAlpha && trueAlpha > MinAlpha);
964  }
965 
966  if (NumEdges > 0) {
967  MAE[t-1].Val2 += CurrentMAE / ((double)(NumEdges*Network.GetNodes()));
968  MSE[t-1].Val2 += CurrentMSE / ((double)(NumEdges*Network.GetNodes()));
969  PrecisionRecall[t-1].Val1 += CurrentPrecisionRecall.Val1/(double)(NumEdges*Network.GetNodes());
970  }
971 
972  if (CurrentAccD > 0) {
973  PrecisionRecall[t-1].Val2 += (1.0 - CurrentPrecisionRecall.Val2 / CurrentAccD)/(double)Network.GetNodes();
974  } else {
975  PrecisionRecall[t-1].Val2 += 1.0/(double)Network.GetNodes();
976  }
977 
978  Accuracy[t-1].Val2 = 1.0 - (1.0-PrecisionRecall[t-1].Val2)/(PrecisionRecall[t-1].Val2 * (1.0/PrecisionRecall[t-1].Val2 + 1.0/PrecisionRecall[t-1].Val1)) - (1.0-PrecisionRecall[t-1].Val1)/(PrecisionRecall[t-1].Val1* (1.0/PrecisionRecall[t-1].Val2 + 1.0/PrecisionRecall[t-1].Val1));
979 }
980 
981 void TNIBs::SaveInferredPajek(const TStr& OutFNm, const double& Step, const TIntV& NIdV) {
982  TFOut FOut(OutFNm);
983  FOut.PutStr(TStr::Fmt("*Vertices %d\r\n", NodeNmH.Len()));
984  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
985  if (NIdV.Len() > 0 && !NIdV.IsIn(NI.GetKey())) { continue; }
986 
987  FOut.PutStr(TStr::Fmt("%d \"%s\" ic Blue\r\n", NI.GetKey().Val+1, NI.GetDat().Name.CStr()));
988  }
989  FOut.PutStr("*Arcs\r\n");
990  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
991  if (NIdV.Len() > 0 && (!NIdV.IsIn(EI.GetSrcNId()) || !NIdV.IsIn(EI.GetDstNId()))) { continue; }
992  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
993 
994  double inferredAlpha = 0.0;
995  if (EI().IsKey(Step)) { inferredAlpha = EI().GetDat(Step); }
996 
997  if (inferredAlpha > MinAlpha) {
998  FOut.PutStr(TStr::Fmt("%d %d %f\r\n", EI.GetSrcNId()+1, EI.GetDstNId()+1, (inferredAlpha > MaxAlpha? MaxAlpha.Val : inferredAlpha)));
999  }
1000  }
1001 }
1002 
1003 void TNIBs::SaveInferred(const TStr& OutFNm, const TIntV& NIdV) {
1004  TFOut FOut(OutFNm);
1005 
1006  // write nodes to file
1007  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1008  if (NIdV.Len() > 0 && !NIdV.IsIn(NI.GetKey())) { continue; }
1009 
1010  FOut.PutStr(TStr::Fmt("%d,%s\r\n", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1011  }
1012 
1013  FOut.PutStr("\r\n");
1014 
1015  // write edges to file (not allowing self loops in the network)
1016  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
1017  if (NIdV.Len() > 0 && (!NIdV.IsIn(EI.GetSrcNId()) || !NIdV.IsIn(EI.GetDstNId()))) { continue; }
1018  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1019 
1020  // not allowing self loops in the Kronecker network
1021  if (EI.GetSrcNId() != EI.GetDstNId()) {
1022  if (EI().Len() > 0) {
1023  TStr Line; bool IsEdge = false;
1024  for (int i=0; i<EI().Len(); i++) {
1025  if (EI()[i]>MinAlpha) {
1026  Line += TStr::Fmt(",%f,%f", EI().GetKey(i).Val, (EI()[i] > MaxAlpha? MaxAlpha.Val : EI()[i].Val) );
1027  IsEdge = true;
1028  } else { // we write 0 explicitly
1029  Line += TStr::Fmt(",%f,0.0", EI().GetKey(i).Val);
1030  }
1031  }
1032  // if none of the alphas is bigger than 0, no edge is written
1033  if (IsEdge) {
1034  FOut.PutStr(TStr::Fmt("%d,%d", EI.GetSrcNId(), EI.GetDstNId()));
1035  FOut.PutStr(Line);
1036  FOut.PutStr("\r\n");
1037  }
1038  }
1039  else
1040  FOut.PutStr(TStr::Fmt("%d,%d,1\r\n", EI.GetSrcNId(), EI.GetDstNId()));
1041  }
1042  }
1043 }
1044 
1045 void TNIBs::SaveInferred(const TStr& OutFNm, const double& Step, const TIntV& NIdV) {
1046  TFOut FOut(OutFNm);
1047 
1048  // write nodes to file
1049  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1050  if (NIdV.Len() > 0 && !NIdV.IsIn(NI.GetKey())) { continue; }
1051 
1052  FOut.PutStr(TStr::Fmt("%d,%s\r\n", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1053  }
1054  FOut.PutStr("\r\n");
1055 
1056  // write edges to file (not allowing self loops in the network)
1057  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
1058  if (NIdV.Len() > 0 && (!NIdV.IsIn(EI.GetSrcNId()) || !NIdV.IsIn(EI.GetDstNId()))) { continue; }
1059  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1060 
1061  // not allowing self loops in the Kronecker network
1062  if (EI.GetSrcNId() != EI.GetDstNId()) {
1063  double inferredAlpha = 0.0;
1064  if (EI().IsKey(Step)) { inferredAlpha = EI().GetDat(Step); }
1065 
1066  if (inferredAlpha > MinAlpha) {
1067  FOut.PutStr(TStr::Fmt("%d,%d,%f\r\n", EI.GetSrcNId(), EI.GetDstNId(), (inferredAlpha > MaxAlpha? MaxAlpha.Val : inferredAlpha)));
1068  }
1069  }
1070  }
1071 }
1072 
1073 void TNIBs::SaveInferredEdges(const TStr& OutFNm) {
1074  TFOut FOut(OutFNm);
1075 
1076  // write edges to file (not allowing self loops in the network)
1077  for (TStrFltFltHNEDNet::TEdgeI EI = InferredNetwork.BegEI(); EI < InferredNetwork.EndEI(); EI++) {
1078  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1079 
1080  // not allowing self loops in the Kronecker network
1081  if (EI.GetSrcNId() != EI.GetDstNId()) {
1082  if (EI().Len() > 0) {
1083  TStr Line; bool IsEdge = false;
1084  for (int i=0; i<EI().Len(); i++) {
1085  if (EI()[i]>MinAlpha) {
1086  Line += TStr::Fmt(",%f,%f", EI().GetKey(i).Val, (EI()[i] > MaxAlpha? MaxAlpha.Val : EI()[i].Val) );
1087  IsEdge = true;
1088  } else { // we write 0 explicitly
1089  Line += TStr::Fmt(",%f,0.0", EI().GetKey(i).Val);
1090  }
1091  }
1092  // if none of the alphas is bigger than 0, no edge is written
1093  if (IsEdge) {
1094  FOut.PutStr(TStr::Fmt("%d,%d", EI.GetSrcNId(), EI.GetDstNId()));
1095  FOut.PutStr(Line);
1096  FOut.PutStr("\r\n");
1097  }
1098  }
1099  else
1100  FOut.PutStr(TStr::Fmt("%d,%d,1\r\n", EI.GetSrcNId(), EI.GetDstNId()));
1101  }
1102  }
1103 }
1104 
1105 void TNIBs::SaveGroundTruth(const TStr& OutFNm) {
1106  TFOut FOut(OutFNm);
1107 
1108  // write nodes to file
1109  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1110  FOut.PutStr(TStr::Fmt("%d,%s\r\n", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1111  }
1112 
1113  FOut.PutStr("\r\n");
1114 
1115  // write edges to file (not allowing self loops in the network)
1116  for (TStrFltFltHNEDNet::TEdgeI EI = Network.BegEI(); EI < Network.EndEI(); EI++) {
1117  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1118 
1119  // not allowing self loops in the Kronecker network
1120  if (EI.GetSrcNId() != EI.GetDstNId()) {
1121  if (EI().Len() > 0) {
1122  FOut.PutStr(TStr::Fmt("%d,%d,", EI.GetSrcNId(), EI.GetDstNId()));
1123  for (int i=0; i<EI().Len()-1; i++) { FOut.PutStr(TStr::Fmt("%f,%f,", EI().GetKey(i).Val, EI()[i].Val)); }
1124  FOut.PutStr(TStr::Fmt("%f,%f", EI().GetKey(EI().Len()-1).Val, EI()[EI().Len()-1].Val));
1125  FOut.PutStr("\r\n");
1126  }
1127  else
1128  FOut.PutStr(TStr::Fmt("%d,%d,1\r\n", EI.GetSrcNId(), EI.GetDstNId()));
1129  }
1130  }
1131 }
1132 
1133 void TNIBs::SaveGroundTruthPajek(const TStr& OutFNm, const double& Step) {
1134  TFOut FOut(OutFNm);
1135 
1136  FOut.PutStr(TStr::Fmt("*Vertices %d\r\n", NodeNmH.Len()));
1137  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1138  FOut.PutStr(TStr::Fmt("%d \"%s\" ic Blue\r\n", NI.GetKey().Val+1, NI.GetDat().Name.CStr()));
1139  }
1140  FOut.PutStr("*Arcs\r\n");
1141  for (TStrFltFltHNEDNet::TEdgeI EI = Network.BegEI(); EI < Network.EndEI(); EI++) {
1142  if (!NodeNmH.IsKey(EI.GetSrcNId()) || !NodeNmH.IsKey(EI.GetDstNId())) { continue; }
1143  double trueAlpha = 0.0;
1144  if (EI().IsKey(Step)) { trueAlpha = EI().GetDat(Step); }
1145  else { for (int j=0; j<EI().Len() && EI().GetKey(j)<=Step; j++) { trueAlpha = EI()[j]; } }
1146 
1147  if (trueAlpha > MinAlpha) {
1148  FOut.PutStr(TStr::Fmt("%d %d %f\r\n", EI.GetSrcNId()+1, EI.GetDstNId()+1, (trueAlpha > MaxAlpha? MaxAlpha.Val : trueAlpha)));
1149  }
1150  }
1151 }
1152 
1153 void TNIBs::SaveSites(const TStr& OutFNm, const TIntFltVH& CascadesPerNode) {
1154  TFOut FOut(OutFNm);
1155 
1156  // write nodes to file
1157  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1158  FOut.PutStr(TStr::Fmt("%d,%s", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1159  if (CascadesPerNode.IsKey(NI.GetKey().Val)) {
1160  for (int i=0; i<CascadesPerNode.GetDat(NI.GetKey().Val).Len(); i++) {
1161  FOut.PutStr(TStr::Fmt(",%f", CascadesPerNode.GetDat(NI.GetKey().Val)[i].Val));
1162  }
1163  }
1164  FOut.PutStr("\r\n");
1165  }
1166 }
1167 
1168 void TNIBs::SaveCascades(const TStr& OutFNm) {
1169  TFOut FOut(OutFNm);
1170 
1171  // write nodes to file
1172  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
1173  FOut.PutStr(TStr::Fmt("%d,%s\r\n", NI.GetKey().Val, NI.GetDat().Name.CStr()));
1174  }
1175 
1176  FOut.PutStr("\r\n");
1177 
1178  // write cascades to file
1179  for (THash<TInt, TCascade>::TIter CI = CascH.BegI(); CI < CascH.EndI(); CI++) {
1180  TCascade &C = CI.GetDat();
1181  int j = 0;
1182  for (THash<TInt, THitInfo>::TIter NI = C.NIdHitH.BegI(); NI < C.NIdHitH.EndI(); NI++) {
1183  if (!NodeNmH.IsKey(NI.GetDat().NId)) { continue; }
1184  if (j > 0) { FOut.PutStr(TStr::Fmt(",%d,%f", NI.GetDat().NId.Val, NI.GetDat().Tm.Val)); }
1185  else { FOut.PutStr(TStr::Fmt("%d;%d,%f", CI.GetKey().Val, NI.GetDat().NId.Val, NI.GetDat().Tm.Val)); }
1186  j++;
1187  }
1188 
1189  if (j >= 1)
1190  FOut.PutStr(TStr::Fmt("\r\n"));
1191  }
1192 }
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:708
#define IAssert(Cond)
Definition: bd.h:262
void BSG(const int &NId, const int &Iters, const TFltV &Steps, const int &BatchLen, const TSampling &Sampling, const TStr &ParamSampling=TStr(""), const bool &PlotPerformance=false)
void SaveGroundTruth(const TStr &OutFNm)
void SaveInferred(const TStr &OutFNm, const TIntV &NIdV=TIntV())
void Randomize()
Definition: dt.h:60
TNodeInfo GetNodeInfo(const int &NId) const
Definition: cascdynetinf.h:217
TIntIntPrH SampledCascadesH
Definition: cascdynetinf.h:166
void SaveGroundTruthPajek(const TStr &OutFNm, const double &Step)
TFlt Mu
Definition: cascdynetinf.h:153
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:898
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the network.
Definition: network.h:758
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TFlt TotalTime
Definition: cascdynetinf.h:147
bool IsIn(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:828
void Init(const TFltV &Steps)
THash< TInt, TCascade > CascH
Definition: cascdynetinf.h:132
unsigned int uint
Definition: bd.h:11
THash< TInt, THitInfo >::TIter EndI() const
Definition: cascdynetinf.h:102
int Len() const
Definition: cascdynetinf.h:97
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:836
TStrFltFltHNEDNet Network
Definition: cascdynetinf.h:141
TStrFltFltHNEDNet InferredNetwork
Definition: cascdynetinf.h:158
TFlt MaxAlpha
Definition: cascdynetinf.h:155
void LoadInferredNodesTxt(TSIn &SIn)
TIter BegI() const
Definition: hash.h:213
void LoadCascadesTxt(TSIn &SIn)
Definition: cascdynetinf.cpp:4
double Val
Definition: dt.h:1385
Definition: fl.h:319
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash< TInt, TNodeInfo > NodeNmH
Definition: cascdynetinf.h:133
TModel
Definition: cascdynetinf.h:7
void AddCasc(const TStr &CascStr, const TModel &Model=EXP)
TFlt Window
Definition: cascdynetinf.h:147
void LoadGroundTruthTxt(TSIn &SIn)
double GetRayleigh(const double &Sigma)
Definition: dt.h:50
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
THash< TInt, THitInfo > NIdHitH
Definition: cascdynetinf.h:87
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
bool GetEDat(const int &SrcNId, const int &DstNId, TEdgeData &EdgeDat) const
Returns edge data in Data for the edge from node IDs SrcNId to DstNId.
Definition: network.h:953
TIter EndI() const
Definition: hash.h:218
void GetInferredGraphAtT(const double &Step, PNGraph &GraphAtT)
static TRnd Rnd
Definition: dt.h:1143
TIntFltH AveDiffAlphas
Definition: cascdynetinf.h:162
const TKey & GetKey() const
Definition: hash.h:80
void SaveInferredPajek(const TStr &OutFNm, const double &Step, const TIntV &NIdV=TIntV())
double GetMinTm() const
Definition: cascdynetinf.h:106
TFlt Delta
Definition: cascdynetinf.h:150
Definition: fl.h:58
static PNet New()
Static constructor that returns a pointer to the network. Call: TPt > Net = TNodeEDatNet::New().
Definition: network.h:661
TFltPrV PrecisionRecall
Definition: cascdynetinf.h:169
double GetTm(const int &NId) const
Definition: cascdynetinf.h:104
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the network.
Definition: network.h:906
TFlt MinAlpha
Definition: cascdynetinf.h:155
TFlt Gamma
Definition: cascdynetinf.h:153
void Clr(const bool &DoDel=true, const bool &ResetDat=true)
Deletes all nodes and edges from the network.
Definition: network.h:786
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
const TDat & GetDat() const
Definition: hash.h:81
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:714
double GetExpDev()
Definition: dt.cpp:83
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the network.
Definition: network.h:756
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
TOptMethod
Definition: cascdynetinf.h:27
TFltPrV MSE
Definition: cascdynetinf.h:170
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:939
TVVec< TFlt > TFltVV
Definition: ds.h:2402
void SG(const int &NId, const int &Iters, const TFltV &Steps, const TSampling &Sampling, const TStr &ParamSampling=TStr(""), const bool &PlotPerformance=false)
uint GetAbsSecs() const
Definition: tm.h:150
static double Power(const double &Base, const double &Exponent)
Definition: xmath.h:25
void LoadInferredTxt(TSIn &SIn)
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void GenCascade(TCascade &C)
void ComputePerformanceNId(const int &NId, const int &Step, const TFltV &Steps)
void FG(const int &NId, const int &Iters, const TFltV &Steps)
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the network.
Definition: network.h:777
TStrIntH DomainsIdH
Definition: cascdynetinf.h:134
TSizeTy GetRows() const
Definition: ds.h:2251
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TFlt InitAlpha
Definition: cascdynetinf.h:155
void SaveSites(const TStr &OutFNm, const TIntFltVH &CascadesPerNode=TIntFltVH())
TFltPrV Accuracy
Definition: cascdynetinf.h:170
void SaveInferredEdges(const TStr &OutFNm)
void GetInferredNetworkAtT(const double &Step, PStrFltNEDNet &NetworkAtT)
bool IsNodeNm(const int &NId) const
Definition: cascdynetinf.h:218
void Clr()
Definition: cascdynetinf.h:95
void GetGroundTruthNetworkAtT(const double &Step, PStrFltNEDNet &NetworkAtT)
void Reset()
Definition: tm.h:81
Definition: ds.h:32
TFlt Aging
Definition: cascdynetinf.h:153
static double GetMn(const double &Flt1, const double &Flt2)
Definition: dt.h:1434
void UpdateDiff(const TOptMethod &OptMethod, const int &NId, TCascade &Cascade, TIntPrV &AlphasToUpdate, const double &CurrentTime=TFlt::Mx)
void find_C(int t, TFltV &x, TFltVV &C, const int &k, const double &s, const double &gamma, const double &T)
THash< TInt, THitInfo >::TIter BegI() const
Definition: cascdynetinf.h:101
Definition: dt.h:412
void LoadGroundTruthNodesTxt(TSIn &SIn)
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TFltPrV MAE
Definition: cascdynetinf.h:170
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
Definition: hash.h:97
TRegularizer Regularizer
Definition: cascdynetinf.h:154
void LabelBurstAutomaton(const int &SrcId, const int &DstId, TIntV &state_labels, TFltV &state_times, const bool &inferred=false, const int &k=5, const double &s=2.0, const double &gamma=1.0, const TSecTm &MinTime=TSecTm(), const TSecTm &MaxTime=TSecTm())
double GetUniDev()
Definition: dt.h:30
TVal1 Val1
Definition: ds.h:34
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 SaveCascades(const TStr &OutFNm)
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSampling
Definition: cascdynetinf.h:40
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
void Sort()
Definition: cascdynetinf.h:110
TSizeTy GetCols() const
Definition: ds.h:2252
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void AddNodeNm(const int &NId, const TNodeInfo &Info)
Definition: cascdynetinf.h:215
THash< TInt, TIntFltH > DiffAlphas
Definition: cascdynetinf.h:163
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
void GetGroundTruthGraphAtT(const double &Step, PNGraph &GraphAtT)
bool IsNode(const int &NId) const
Definition: cascdynetinf.h:109
double GetPowerDev(const double &AlphaSlope)
Definition: dt.h:47
void find_min_state(TFltVV &C, TIntV &states, const int &k, const double &s, const double &gamma, const double &T)
static TRnd Rnd
Definition: dt.h:1393
TModel Model
Definition: cascdynetinf.h:144
TFlt Tol
Definition: cascdynetinf.h:155
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:680
bool GetNextLn(TStr &LnStr)
Definition: fl.cpp:43
TIntFltH TotalCascadesAlpha
Definition: cascdynetinf.h:159
void SortByDat(const bool &Asc=true)
Definition: hash.h:292