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
anf.cpp
Go to the documentation of this file.
1 // Approximate Neighborhood Function
3 namespace TSnap {
4 namespace TSnapDetail {
5 
6 // interpolate effective diameter
7 double CalcEffDiam(const TIntFltKdV& DistNbrsCdfV, const double& Percentile) {
8  const double EffPairs = Percentile * DistNbrsCdfV.Last().Dat;
9  int ValN;
10  for (ValN = 0; ValN < DistNbrsCdfV.Len(); ValN++) {
11  if (DistNbrsCdfV[ValN].Dat() > EffPairs) { break; }
12  }
13  if (ValN >= DistNbrsCdfV.Len()) return DistNbrsCdfV.Last().Key;
14  if (ValN == 0) return 1;
15  // interpolate
16  const double DeltaNbrs = DistNbrsCdfV[ValN].Dat - DistNbrsCdfV[ValN-1].Dat;
17  if (DeltaNbrs == 0) return DistNbrsCdfV[ValN].Key;
18  return DistNbrsCdfV[ValN-1].Key + (EffPairs - DistNbrsCdfV[ValN-1].Dat)/DeltaNbrs;
19 }
20 
21 double CalcEffDiam(const TFltPrV& DistNbrsCdfV, const double& Percentile) {
22  TIntFltKdV KdV(DistNbrsCdfV.Len(), 0);
23  for (int i = 0; i < DistNbrsCdfV.Len(); i++) {
24  KdV.Add(TIntFltKd(int(DistNbrsCdfV[i].Val1()), DistNbrsCdfV[i].Val2));
25  }
26  return CalcEffDiam(KdV, Percentile);
27 }
28 
29 double CalcEffDiamPdf(const TIntFltKdV& DistNbrsPdfV, const double& Percentile) {
30  TIntFltKdV CdfV;
31  TGUtil::GetCdf(DistNbrsPdfV, CdfV);
32  return CalcEffDiam(CdfV, Percentile);
33 }
34 
35 double CalcEffDiamPdf(const TFltPrV& DistNbrsPdfV, const double& Percentile) {
36  TFltPrV CdfV;
37  TGUtil::GetCdf(DistNbrsPdfV, CdfV);
38  return CalcEffDiam(CdfV, Percentile);
39 }
40 
41 double CalcAvgDiamPdf(const TIntFltKdV& DistNbrsPdfV) {
42  double Paths=0, SumLen=0;
43  for (int i = 0; i < DistNbrsPdfV.Len(); i++) {
44  SumLen += DistNbrsPdfV[i].Key * DistNbrsPdfV[i].Dat;
45  Paths += DistNbrsPdfV[i].Dat;
46  }
47  return SumLen/Paths;
48 }
49 
50 double CalcAvgDiamPdf(const TFltPrV& DistNbrsPdfV) {
51  double Paths=0, SumLen=0;
52  for (int i = 0; i < DistNbrsPdfV.Len(); i++) {
53  SumLen += DistNbrsPdfV[i].Val1 * DistNbrsPdfV[i].Val2;
54  Paths += DistNbrsPdfV[i].Val2;
55  }
56  return SumLen/Paths;
57 }
58 
59 } // namespace TSnapDetail
60 } // namespace TSnap
61 
Main namespace for all the Snap global entities.
Definition: alg.h:1
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:381
double CalcEffDiamPdf(const TIntFltKdV &DistNbrsPdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) probability distribution functio...
Definition: anf.cpp:29
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
static void GetCdf(const TIntPrV &PdfV, TIntPrV &CdfV)
Definition: util.cpp:3
double CalcAvgDiamPdf(const TIntFltKdV &DistNbrsPdfV)
Helper function for computing the mean of a (unnormalized) probability distribution function...
Definition: anf.cpp:41
double CalcEffDiam(const TIntFltKdV &DistNbrsCdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function...
Definition: anf.cpp:7
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430