







































\section{Parallel and Distributed version of\\ {\sc{propagate-s}}}

\paragraph{Neighborhood Function estimation on huge graphs}\label{apx:huge_graph_est}
In Table \ref{tab::stress_test_map_red}, we show the execution time of {\sc{propagate-s}}~ distributed on a cluster of $8$ identical machines (see Section \ref{sec:exp_setting} for the server specifics). In this experiment, every server has the whole graph. As a first step, a map function assigns a disjoint subset of seeds to every machine. Then, Algorithm \ref{SE-MHSE} is executed by server with the given set of seeds. When the execution of {\sc{propagate-s}}~ reaches line 21, the server \emph{emits} the triple: $\langle \texttt{CountAll, r, MaxHop} \rangle$ i.e., the  number of \emph{collisions} at each hop, number of performed hops, and the diameter lower bound. Once all the servers have emitted a triple for each assigned seed, we compute the distance metrics in a centralized fashion. We observe that distributing the load on more than one machine gives a massive speed up of the estimation process. Moreover, {\sc{propagate-s}}~ needs about $21$ hours to estimate the distance metrics on \texttt{eu-2015}, i.e. the largest web-crawl available on \texttt{WebGraph}~\cite{BoVWFI}. 
\input{Tabelle/stress_test_map_red}
\paragraph{Computation of the exact Neighborhood Function}\label{apx:gt_dist} In Table \ref{tab::gt_times_map_reduce}, we show {\sc{propagate-s}}'s execution times for computing the ground-truth metrics of the first group of graphs in Table \ref{tab::sparsityAnddatasetdim} on a cluster of $8$ identical machines. We observe that distributing the workload on $8$ machines gives a massive speed-up for the computation of the exact neighborhood function. We conclude that {\sc{propagate-s}}~ can be easily used to retrieve the exact distance metrics on very big graphs. Indeed, due to its space efficiency, it does not need a cluster of first-class servers with hundred of gigabytes of memory each. Moreover, it could be used with a cluster of average machines equipped with $16$ or $32$GB of memory. 
\input{Tabelle/gt_map_reduce}


\section{Conclusions}
\label{Sec:conclusion}
We propose {\sc{propagate}}, a novel framework for estimating distance-based metrics on very large graphs. So far the framework can approximate: average distance, (effective) diameter, and number of reachable pairs and the connectivity rate. 
We provide theoretical error bounds of the quality of the approximation for such metrics. Indeed,
$\Theta\left(\frac{\log n}{\varepsilon^2}\right)$ sample nodes for any constant $\varepsilon>0$, are enough to approximate within: (1) $\xi = \frac{\varepsilon\cdot \Delta}{\alpha}$ the average distance; (2) $\xi = \frac{\varepsilon}{\alpha}$ the diameter and effective diameter; and, (3) $\xi = \varepsilon$ the connectivity rate $\alpha$.
We derive two different algorithms from the {\sc{propagate}}~ framework: {\sc{propagate-p}}, and {\sc{propagate-s}}.
Both algorithms run in time $\mathcal{O}(\frac{\ln n}{\varepsilon^2}\cdot\Delta\cdot m)$. For the space complexity, {\sc{propagate-p}}~ and {\sc{propagate-s}}~ requires $\mathcal{O}\left(n\frac{\log n}{\varepsilon^2}+m\right)$ and $\mathcal{O}(n+m)$ space, respectively. 
We prove both theoretically and experimentally, that {\sc{propagate}}~ significantly improves the state of the art. Compared to its competitors (HyperANF~ \cite{Boldi:2011:HAN}, and \textsc{MHSE} \cite{BIGDATA2017}), {\sc{propagate-p}}~ and {\sc{propagate-s}}~ are more efficient in terms of space and and execution time. Indeed, {\sc{propagate-p}}~ needs $s\cdot n\sim\frac{n\log n}{\varepsilon^2}$ bits and {\sc{propagate-s}}~ $n$ bits for the registers. While, HyperANF~ and \textsc{MHSE} use for the registers, respectively: $2\cdot s\cdot n\cdot \log_2\log_2 \left(n/s\right)$, and $2\cdot s\cdot n\cdot \log_2 n$ bits. The implementation that uses single and simple bitwise operations to merge the neighborhoods, and to thus to count the collisions, yield a lower execution time of {\sc{propagate-p}}~ with respect to HyperANF~ and \textsc{MHSE}. We experimentally verified that {\sc{propagate}}~ framework is, in general, faster and more effective than HyperANF~ and \textsc{MHSE} on, real directed and undirected graphs. Indeed, our novel framework produces statistically significant estimations on most of the analyzed networks. Moreover, {\sc{propagate-p}}~ is $60\%$ faster than HyperANF, and $81\%$ faster than \textsc{MHSE}. From our experiments, we deduced that {\sc{propagate-s}}~ is the only algorithm that can be used to estimate the neighborhood function of graphs with billion nodes.
{\sc{propagate}}~ relies on \emph{unbiased} estimators to approximate the distance-metrics. Thus, it can be used to compute their \emph{exact} values.  
Experimentally, for this task, {\sc{propagate-s}}~ turned out to be more efficient than \texttt{WebGraph}'s \textsc{APSP} algorithm on almost all  the analyzed real-world graphs.
Finally, we developed an open source  framework in Java\footnote{\href{https://github.com/BigDataLaboratory/MHSE}{github.com/BigDataLaboratory/MHSE}} that allows every user with an average laptop to approximate the neighborhood function on big graphs. As future works, we plan to use {\sc{propagate}}~ to compute the centrality measures on vertices and edges and to extend its applications to community detection tasks.


\section{Experimental Evaluation}
\label{Sec:tool}

In this section, we summarize the results of our experimental study on approximating the distance based metrics in real-world networks. We employ a set of competitor algorithms, for which the authors provided an open source version of their code, that we can use to approximate the distance metrics, i.e., for each algorithm, we compute  the \emph{average distance, effective diameter,} and \emph{number of reachable pairs}. Subsequently, we evaluate (using various metrics) how these estimates relates to the \emph{exact} ones computed by the All Pairs Shortest Path algorithm.


\subsection{Experimental Setting}\label{sec:exp_setting}

\paragraph{Algorithms.} Our study
includes several competitor algorithms for approximating the neighborhood function. We provide a short description and a space complexity analysis of the considered algorithms.
\begin{description}
    \item [\normalfont{\textsc{HyperANF:}}] The algorithm of Boldi et al. \cite{Boldi:2011:HAN,BoVWFI}, which uses HyperLogLog algorithms~\cite{DurandFlajolet2003,Flajolet07hyperloglog} to approximate the neighborhood function. HyperANF~ requires for each node $2^b = s$ registers that records the position $R$ with the bit $1$ starting the tail ending with all $0s$. More precisely, if $n$ is the number of distinct nodes in the graph, HyperANF~ needs $2\cdot s\cdot n\cdot \log_2\left(\log_2\left(n/s\right)\right)$ bits.
    \item [\normalfont{\textsc{MHSE:}}] The algorithm of Amati et al. \cite{BIGDATA2017}, which uses the MinHash counter to approximate the neighborhood function. \textsc{MHSE} is based on a BFS visit and it requires an $\mathcal{O}(\log n)$ register for each node to record the signature, hence, it has the same space complexity as \textsc{ANF} (\textsc{ANF} maintains a bitwise $\mathcal{O}(\log n)$ register to count new incoming nodes in the stream, instead). \textsc{MHSE} needs $2\cdot s\cdot n \cdot \log_2 n$ bits.
    \item [\normalfont{{\sc{propagate-p}}:}] The algorithm described in Section \ref{Section:MHSE} for computing the distance based metrics. {\sc{propagate-p}}~ needs $n\cdot s$ bits because every node has a register of exactly $s$ bits. 
    \item [\normalfont{{\sc{propagate-s}}:}] The algorithm described in Section \ref{Section:SE-MHSE}.{\sc{propagate-s}}~ needs only $n$ bits ($1$ bit for every node in the graph). 
    \item [\normalfont{APSP:}] The Java implementation of the All Pair Shortest Path algorithm. available in \texttt{WebGraph}\cite{BoVWFI}. The algorithm has been used to compute the exact values of the distance metrics and as a competitor algorithm for the second part of the experimental evaluation.
\end{description}



\paragraph{Networks}
\label{Sec:experimentation}
We evaluate all of the above competitors on real-world graphs of different nature, whose properties are summarized in Table \ref{tab::sparsityAnddatasetdim}. The networks come from two different domains: social networks and web-crawls. According to Theorem \ref{th:MHSE-Error}, the collection \texttt{BlackFriday}\footnote{The BlackFriday graph
is built from Twitter considering retweet and reply activities (\cite{IADIS2016}). This graph is comparable in size to the largest publicly available social network graphs, and  is very sparse.} should require larger number of samples than other collections,  because of a small connectivity rate  (see Table \ref{tab::sparsityAnddatasetdim}). Additionally, \texttt{web-BerkStan} and \texttt{Orkut}, due to their long diameters,  should require a larger sample for the computation of the average distance. Indeed, these facts are experimentally shown on Figure \ref{fig:increment_undirected}, where a small number of samples may lead to poor results for such collections.

\input{Tabelle/subset_graphs}


\paragraph{Implementation and Evaluation details.} We released an open source platform for analyzing large graphs. This tool is developed in Java and uses some WebGraph libraries~\cite{BoVWFI} to load and parse the  graph in compressed form. We chose WebGraph both for benchmarking with the compared algorithms and to allow us to: (1) compress very large graphs; (2) iterate the neighbor list of a node with faster random access; and, (3) use its offline methods to process very big graphs that cannot be loaded in memory. We executed the experiments on a server running Ubuntu 16.04.5 LTS equipped with AMD Opteron 6376 CPU (2.3GHz) for overall 32 cores and 64 GB of RAM. All the algorithms are fairly compared, i.e. using the same number of seeds and cores. For the comparison between {\sc{propagate}}, HyperANF, and \textsc{MHSE} we use 256 sample nodes and 256 registers and 32 cores. For the comparison between {\sc{propagate-s}}~ and APSP we use 32 cores. For the first part of the experiments, we repeat every test $10$ times and average over the results for every algorithm (HyperANF, \textsc{MHSE}, {\sc{propagate-p}}, and {\sc{propagate-s}}). Whenever we show a residual $(\hat{x}-\tilde{x})/\hat{x}$ where $\hat{x}$ is the \emph{{exact} }, value and $\tilde{x}$ its \emph{estimate} we exhibit a p-value. More precisely, we perform a two-sided unpaired \emph{t-test} \cite{Case_Berg_2001} with confidence interval of $0.95$. Given a set $X$ of estimates of the distance metric $y$ obtained after $10$ runs of an algorithm $\mathcal{A}$, the null hypothesis is that its mean $\overline{X}$ is equal to the exact value $X$. If the displayed p-value is in the range $[0.9,1.0]$ then we fail to reject the null hypothesis, and conclude that the means are not significantly different. Therefore, we can conclude that algorithm $\mathcal{A}$ provides reliable and statistically significant estimates of $y$.
\subsection{Experimental Results}
\label{sec:exper_res}
\paragraph{Accuracy and effectiveness}
In our first experiment, we run on the networks listed in the first group of Table \ref{tab::sparsityAnddatasetdim} all the discussed approximation algorithms. More precisely, on each data set, we run every algorithm $10$ times using $256$ registers/seeds. We then, for each of these four algorithms ({\sc{propagate-p}},{\sc{propagate-s}},HyperANF, plus \textsc{MHSE}): (1) compute the average of all the three estimated quantities (average distance, effective diameter, and number of reachable pairs); (2) evaluate the (average) precision (of every algorithm for every distance metric) by computing the residuals between the exact and the estimated values; and, (3) perform a two-sided unpaired \emph{t-test} between the vector of estimated values and the \emph{exact} distance metric of interest to evaluate the effectiveness of the algorithm.
In Table \ref{Experiment1}, we show the accuracy and effectiveness of all the competitor algorithms. Moreover, {\sc{propagate-p}}~ and {\sc{propagate-s}}~ are grouped under the name of {\sc{propagate}}, that is because both algorithm produce the same results. We observe that {\sc{propagate}}~ provides more accurate estimations compared to its competitors. In general {\sc{propagate}}, and HyperANF~ perform very close (see Table \ref{Experiment1}). However, our novel framework provides smaller residuals and statistically significant estimations on most of the data sets.

For the average distance, {\sc{propagate}}'s estimations have smaller residuals (almost $0.0$) on $9$ over $13$ graphs, while HyperANF~ performs better only on $4$ graphs (notice that for these data sets {\sc{propagate}}~ still provides precise estimations). Furthermore, \textsc{MHSE} produces worst approximations for the instances on which it was possible to run the algorithm. {\sc{propagate}}~ and HyperANF~ perform closely in terms of quality of the approximation. However, our framework has higher p-values on most of the analyzed graphs.

For the effective diameter, {\sc{propagate}}~ gives very accurate estimations and outperform its competitors on $7$ networks. Furthermore, {\sc{propagate}}~ is the one that produces the major number of statistically significant estimations. While HyperANF, and \texttt{MHSE} provide statistically significant estimations for \texttt{Soc-pokec}, and \texttt{Amazon-2008} respectively.

Finally, the best algorithm for estimating the number of reachable pairs, is {\sc{propagate}}. It provides better estimations on $10$ networks over $13$. \textsc{MHSE} instead, has worst performances than our framework but it outperform HyperANF~ which is the algorithm with poorest estimations (indeed it has good residuals only on \texttt{Soc-pokec}). Observe that {\sc{propagate}}~ is the algorithm that provides the higher number of statistically significant estimations. We believe that our novel framework is the best suited for being a probabilistic counter of the set of reachable nodes for both, directed and undirected graphs.
We can conclude that our novel framework is more reliable than the state of the art to estimate the distance based metrics. Indeed, It provides accurate and statistically significant estimations.
 
  

\paragraph{Incremental approach.}

As a second experiment, we aim to better investigate the dependency of {\sc{propagate}}'s perfomance with respect to its sample size. We recall that Theorem \ref{th:MHSE-Error} states that a sample of $\mathcal{O}(\log n)$ nodes is enough to obtain good approximations of the average distance and the effective diameter with high probability, although $256$ seeds give really good approximations (see Table \ref{Experiment1}). Figure \ref{fig:increment_undirected}, shows the performances of the {\sc{propagate}}~ framework with a representative increasing number of seeds, that is  $s=16, 64,128, 256$. The figure shows the average results over $10$ trials. {\sc{propagate}}~ achieves high quality approximations with $64$ seeds even for \texttt{Orkut-2007}, \texttt{web-NotreDame},and \texttt{Web-BerkStan} i.e. the graphs that have low connectivity rate $\alpha$. The {\sc{propagate}}~ framework performs well for each approximation (average distance, effective diameter, and number of reachable pairs) with $64$ seeds on both directed and undirected graphs. More precisely, on directed graphs for all the distance metrics the residual is below $\pm 1\%$ except for \texttt{blackfriday} for which the residual are at most $\pm 2\%$ (see Figure \ref{fig:increment_undirected}). On undirected graphs, the average distance and effective diameter residuals are at most $\pm 1\%$, while for the number of reachable pairs it is exactly $0\%$  except for \texttt{Hollywood-2009} and \texttt{Orkut-2007} that have a residuals of at most $\pm 1\%$ (see the Figure \ref{fig:increment_undirected}). Figure \ref{fig:increment_undirected} (c) shows the effectiveness of the framework as a probabilistic counter of the set of reachable nodes for both, directed and undirected graphs. Therefore, {\sc{propagate-s}}~ can be used with a progressive sampling approach \cite{Riondato_2015}. Indeed we could start with a small sample of nodes and progressively increase it if a certain stopping criterion is not met yet, allowing for an even faster approximation approach.


\begin{figure}[t!]
\centering
	
	\begin{subfigure}[b]{0.4\textwidth}

		\includegraphics[scale=0.45]{Figure/new_residuals/avg_d.png}
		\caption{}

	\end{subfigure}
	
	\begin{subfigure}[b]{0.4\textwidth}
		
		\includegraphics[scale=0.45]{Figure/new_residuals/eff_d.png}
		\caption{}

	\end{subfigure}
	
	\begin{subfigure}[b]{0.4\textwidth}
		
		\includegraphics[scale=0.45]{Figure/new_residuals/coupls.png}
		\caption{}

	\end{subfigure}

	
	

	\caption{Effectiveness of {\sc{propagate}}~ on real world graphs with different number of seeds. Plots of the residuals for: Average Distance, Effective Diameter at 90\% , and Number of Connected Pairs.
		\label{fig:increment_undirected}}
\end{figure}




\paragraph{Speed.}
As a third experiment, we compared the average execution times of {\sc{propagate-p}}, {\sc{propagate-s}}, HyperANF, and \textsc{MHSE}. In Table \ref{tab:estimation_times}, we show the running times (in milliseconds) of the algorithms. We observe that {\sc{propagate}}~ framework outperform its competitors on \emph{every} dataset. Remarkably, {\sc{propagate-p}}, leads the scoreboard with the fastest execution times on all graphs. On average, {\sc{propagate-p}}~ is $60\%$ faster than HyperANF~ and $81\%$ faster than \textsc{MHSE}. Moreover, {\sc{propagate-s}}~ outperform (in terms of speed) HyperANF~ on $6$ networks and \textsc{MHSE} on all the graphs. HyperANF~ is the third fastest algorithm while \textsc{MHSE} is the slowest one. More precisely, \textsc{MHSE} is slower than every other algorithm on every network for which it does not require more than $64GB$ or \textsc{RAM} i.e., does not generate a memory overflow error.

\input{Tabelle/times_subset}

\paragraph{Estimating Distance Metrics on huge graphs.}
As a fourth experiment, we run all the approximation algorithms on the biggest networks available in \cite{LAW} (see the second group of data sets in Table \ref{tab::sparsityAnddatasetdim}). We aim to to investigate the performances of all the competitor algorithms on very big graphs. In Table \ref{tab::stress_test}, we show the running times of the approximation algorithms. The first column indicates if the graph can be fully loaded in memory in its uncompressed form. If this is not possible, we use \texttt{WebGraph}'s offline methods to access the compressed graph from the disk without loading it in memory. Observe that accessing the compressed graph directly from the disk, slows down the overall execution of the algorithms. However, is the only way to analyse these graphs with our $64$GB memory machines. We observe that {\sc{propagate-s}}~ can compute the distance metrics on \emph{every} graph. Considering the size of the data sets, {\sc{propagate-s}}~ requires a reasonable amount of time to approximate the neighborhood function using $256$ seeds. {\sc{propagate-p}}~ can compute the distance metrics for \texttt{it-2004, gsh-2015-host}, and \texttt{sk-2005}. Moreover, it is still possible to run {\sc{propagate-p}}~ on the remaining graphs by appropriately decreasing the number of sample nodes. Instead, HyperANF~ can be used only to compute the approximated neighborhood function only on \texttt{it-2004}, and \texttt{sk-2005}. Finally, \textsc{MHSE} cannot be used on any these networks due to its high space complexity. Before comparing the time performances, we point out that {\color{red}\xmark}~ in Table \ref{tab::stress_test} indicates that the algorithm requires more than $64$GB of memory even with $1$ seed/register. Thus, decreasing the number of seeds/registers is not enough to run these algorithms on these huge networks, we would need to upgrade the RAM of the machine. From the results in Table \ref{tab::stress_test}, we observe that (on \texttt{it-2004}, and \texttt{sk-2005}) {\sc{propagate-p}}~ is on average $64\%$ faster than HyperANF. Furthermore, {\sc{propagate-s}}~ is the best algorithm to approximate the neighborhood function on huge data sets. It requires $n\cdot s$ bits, to store the graph \emph{signature}. Indeed, for \texttt{eu-2015}, i.e. the biggest graph in Table \ref{tab::sparsityAnddatasetdim}, it needs approximately at most $1$GB to store the graph signature. Thus, using \texttt{WebGraph}'s offline methods to scan the graph, {\sc{propagate-s}}~ could provide the approximated neighborhood function of \texttt{eu-2015} using an average \emph{laptop}.

\input{Tabelle/stress_test}

\paragraph{Computing ground truth metrics with {\sc{propagate}}.}
As a last experiment, we compare {\sc{propagate-s}}~ with the \texttt{WebGraph} implementation of the All Pair Shortest Path (\textsc{APSP}) algorithm to compute the \emph{exact} neighborhood function. Among all the competitor algorithms, HyperANF~ cannot be used to compute the ground truth values of a graph. That is because its neighborhood function estimator that uses the \texttt{HyperLogLog} counter is \emph{asymptotically almost unbiased} \cite{Boldi:2011:HAN}. \textsc{MHSE} instead, cannot be employed because of its high space complexity. Conversely, {\sc{propagate}}~'s distance metrics estimators are all \emph{unbiased}. Thus, our novel framework can be used to compute the ground truth values. Given a $n$ vertices graph $G=(V,E)$, {\sc{propagate}}~ suffices of the entire vertex set $V$ as set of seeds to compute the exact distance metrics. For this experiment, we use {\sc{propagate-s}}~ because it needs only $n$ bits to store the graph signature, while {\sc{propagate-p}}~ would need $n^2$ bits and with a $64$GB machine can be used only for computing the ground truth metrics of the first three graphs in Table \ref{tab::sparsityAnddatasetdim}. In Table \ref{tab::gt_times}, we show the running times of {\sc{propagate-s}}~ and \textsc{APSP}. We observe that {\sc{propagate-s}}~ is faster than \texttt{WebGraph}'s \textsc{APSP} implementation on $10$ over $13$ data sets. Overall, our framework is much faster than the \texttt{APSP} algorithm. {\sc{propagate-s}}~ shows worse
performances on few data sets, such as: \texttt{web-NotreDame, web-Google,} and \texttt{web-BerkStan}. These results suggest
that {\sc{propagate-s}}~ is preferable for retrieving exact values of distance-based metrics on very large real-world graphs.
\input{Tabelle/times_gt_subset}

\paragraph{Distributed Neighborhood Function estimation on huge graphs}
In Table \ref{tab::stress_test_map_red}, we show the execution time of {\sc{propagate-s}}~ distributed on a cluster of $8$ identical machines (see Section \ref{sec:exp_setting} for the server specifics). In this experiment, every server has the whole graph. As a first step, a map function assigns a disjoint subset of seeds to every machine. Then, Algorithm \ref{SE-MHSE} is executed by server with the given set of seeds. When the execution of {\sc{propagate-s}}~ reaches line 21, the server \emph{emits} the triple: $\langle \texttt{CountAll, r, MaxHop} \rangle$ i.e., the  number of \emph{collisions} at each hop, number of performed hops, and the diameter lower bound. Once all the servers have emitted a triple for each assigned seed, we compute the distance metrics in a centralized fashion. We observe that distributing the load on more than one machine gives a massive speed up of the estimation process. Moreover, {\sc{propagate-s}}~ needs about $21$ hours to estimate the distance metrics on \texttt{eu-2015}, i.e. the largest web-crawl available on \texttt{WebGraph}~\cite{BoVWFI}. 

\input{Tabelle/stress_test_map_red}


\paragraph{Distributed computation of the exact Neighborhood Function}\label{apx:gt_dist} In Table \ref{tab::gt_times_map_reduce}, we show {\sc{propagate-s}}'s execution times for computing the ground-truth metrics of the first group of graphs in Table \ref{tab::sparsityAnddatasetdim} on a cluster of $8$ identical machines. We observe that distributing the workload on $8$ machines gives a massive speed-up for the computation of the exact neighborhood function. We conclude that {\sc{propagate-s}}~ can be easily used to retrieve the exact distance metrics on very big graphs. Indeed, due to its space efficiency, it does not need a cluster of first-class servers with hundred of gigabytes of memory each. Moreover, it could be used with a cluster of average machines equipped with $16$ or $32$GB of memory. 

\input{Tabelle/gt_map_reduce}


\input{Tabelle/subset_results}

\section{MHSE~ Framework}\label{Sec:MinHash}

\section{{\sc{propagate}}~ Framework}\label{Sec:algorithm}
The {\sc{propagate}}~ framework is based on the same observation as \texttt{ANF} \cite{palmer2002anf}: the neighborhood $N(u,r+1)$ of radius $r+1$ around node $u$ can be derived as follows:
\begin{equation}
\label{Eq:union}
N(u,r+1) = \bigcup _{(u,v)\in E}N(v,r)
\end{equation}
As initial step, the {\sc{propagate}}~ starts by drawing, from $V$, independently and uniformly at random (with replacement) a set
$\{x_1,x_2,$
$\ldots,x_s\}$ of $s$ random nodes (seeds), and assigning  to each node $u\in V$ a Boolean \emph{signature} array $Sig_u[]$ of length $s$ defined as follows: for all $ i\in\{1,\dots s\}$
\[
Sig_u[i] = \left\{
            \begin{array}{ll}
            1 & \text{If } u = x_i\text{ is a seed} \\
            0 & \text{ otherwise}
            \end{array}
            \right.
\; \]

We extend the definition of signature to a set of nodes $N\subseteq V$, as $Sig_N[\;] = \bigvee_{u\in N}{Sig_u[\;]}$, that is the $i$-th index of  $Sig_N[\;]$ is set to $1$ if and only if there exists at least one vertex $u\in N$ such that $Sig_u[i]=1$.

With reference to Algorithm \ref{MHSE-Bool} (lines 7-20) and Algorithm \ref{SE-MHSE} (lines 2-20), {\sc{propagate}}~ framework 
incrementally builds the neighborhood signature at distance $r+1$ by iterating over all the signatures at distance $r$ and keeping track of the number of \emph{collisions} between the signatures (the number of common $1$-valued indices of the two $s$-signatures). Given a node $u\in V$ and the signature of its neighborhood set at hop $r$, we build the signature at hop $r+1$ by using the \textsc{merge} function. Such function computes the signature of a set $S = S_1 \cup S_2$ by performing the \emph{bitwise} \textsc{or} between the signatures of $S_1$ and $S_2$. 
Then, {\sc{propagate}}~ updates the number of new collisions by performing the \textsc{xor} operation between the signature of $N(u,r)$ and $N(u,r+1)$.
The framework stops when there are no more collisions i.e., the signatures do not change between the $k$-th and the $k+1$-th iteration. 
Notice that a collision corresponds to a step  of the Dijkstra's algorithm of SSSP~\cite{Cormen:2009:IAT} for unweighted graphs that places  $r$ at the index of the node $u$ in the array of $u_i$.
























The {\sc{propagate}}~ framework leads to two different implementations: (1) {\sc{propagate-p}}~ (Section ~\ref{Section:MHSE}),  first samples  $s$ nodes and then computes the total number of collisions, as long as  there are no collisions detected during the current hop; (2) {\sc{propagate-s}}~ (Section ~\ref{Section:SE-MHSE}),  is a fully parallel/distributed version of this sampling method. For each sample vertex, it spreads the seed until new collisions are detected. This process is repeated independently $s$ times, and the collisions are collected at the end. 
{\sc{propagate-s}}~ is preferable  to {\sc{propagate-p}}~ when $s$ is very large and $s\cdot n$ bits becomes too big to be kept in the memory of a single machine. For example, when the set of seeds is the entire vertex set $V$, that is $s=|V|$, then {\sc{propagate}}~ computes the \emph{exact} neighborhood function. To compute the ground-truth values, {\sc{propagate-p}}~ needs $n^2$-bit array that, for big graphs, can be too large to be stored on a single machine. {\sc{propagate-s}}, instead,  needs only $n$ bits. Thus, for this task, {\sc{propagate-s}}~ is preferable to {\sc{propagate-p}}~. In Section \ref{sec:exper_res} we compare the execution times of {\sc{propagate-s}} and the All Pair Shortest Path algorithm to compute the \emph{exact} neighborhood function of big real-world graphs.
Note that the base-step of the {\sc{propagate}}~ framework resembles a  BFS-like visit. However, due to the prohibitive dimensions of real-world networks we can not use a textbook breadth first search to propagate seeds in the graph. This is because in a multi-thread implementation (crucial to analyze huge networks) it is impossible to maintain the BFS queue. We opt for a clever ball-like expansion implementation that does not require auxiliary data structures to keep track of the visited vertices.




\subsection{{\sc{propagate-p}}~ Algorithm\label{Section:MHSE}}
Given $s$ sample nodes $\{x_1, \dots, x_{s}\}\subseteq V$, {\sc{propagate-p}}~ (Algorithm \ref{MHSE-Bool}) first initializes (line 2-4) the signature $s$-array for each node $u\in V$, $\texttt{Sig}_u[\;]$  as described in Section \ref{Sec:algorithm}. Subsequently, at each hop $r$, it computes for each node $u$ the \emph{signature} of the ball $N(u,r)= \{v\in V: d(u,v) \leq r\}$. 
The variable $\texttt{Count}$ (line 5) keeps track of the number of new collisions at hop $r$, that is the number of vertices at distance \emph{exactly} $r$ from $u$. The collisions at hop $r$ are subsequently stored in $\texttt{CountAll}[r]$ and if new collisions have been detected during the current hop, then diameter lower-bound $\texttt{MaxHop}$ is updated and the hop $r+1$ is processed (lines 17-19).
Once the stopping criterion is met, i.e. no more collisions have been detected, the algorithm: (1) computes the number of reachable pairs at each hop $r$ (lines 22-23): $R[r]$ contains the number of pairs at distance at most $r$; (2) increases a variable $\texttt{AvgDist}$ with the difference between $R[r]$ and $R[r-1]$ times the hop $r$. Subsequently, normalizes the result by dividing with  the maximum number of reachable pairs i.e. it computes Equation \ref{eq:avg_distance} (lines 24-27); (3) sets the diameter lower bound $\Delta_{\texttt{LB}} $ as the maximum number of performed hops (line 28); (4) finds the minimum hop $r$ such that the ratio between the reachable pairs at hop $r$  and at the maximum hop is greater than $90\%$ i.e., computes the effective diameter $\Delta^{\texttt{eff}}$ (line 29).



Since Algorithm {\sc{propagate-p}}~  can be implemented by using an array of $s$ bits for each vertex then we have the following theorem:
\begin{theorem}
	\label{th:Algo1}
	Algorithm {\sc{propagate-p}}~ (Algorithm \ref{MHSE-Bool}) computes the: diameter, effective diameter, average distance and number of reachable pairs in $\mathcal{O}(s\cdot\Delta\cdot m)$ time using $\mathcal{O}(s\cdot n+m)$ space.
\end{theorem}
\begin{proof}
After the initialization of the node signatures, at every step of the \texttt{do-while}, Algorithm \ref{MHSE-Bool} scans the graph by iterating over the nodes. During iteration $r$, if a node $u\in V$ has at least one of its $s$ signature bits set to $0$, it updates its signature by performing a bitwise \textsc{OR} between its signature and the one of its neighbors. Notice that, once a bit flips to $1$, it cannot go back to $0$. Subsequently, for each node $u\in V$ it counts the number of ``bit-flips'' occurred in the current iteration, and stores the value in \texttt{CountAll}$[r]$. The algorithm stops when the set of bits that change values to $1$ is empty. Notice that a seed $s$ can perform at most $n-1$ hops. Since, at every iteration of the \texttt{do-while} every seed is propagated in parallel, the algorithm iterates for at most $s\cdot \Delta$ steps. Every iteration of the \texttt{do-while} requires at most $\mathcal{O}(m)$ steps. Thus, the time complexity of the loop is $\mathcal{O}(s\cdot \Delta \cdot m)$. Subsequently, the algorithm computes the neighborhood function, the average distance, the diameter and the effective diameter. This can be done in linear time in the diameter of the graph $\Delta$. Algorithm \ref{MHSE-Bool}, needs $s$ bits for each node signature, and two arrays of length $\Delta$ to store the number of collisions at each time step and the neighborhood function. Thus the space required by the algorithm is $\mathcal{O}\left(s\cdot n + m\right)$. The correctness of the algorithm follows from the definition of the {\sc{propagate}}~ framework in Section \ref{Sec:algorithm}.
\end{proof}
\input{./PseudoCodice/MHSE-Bool_G.tex}

\subsection{{\sc{propagate-s}}~ Algorithm\label{Section:SE-MHSE}}

We derive an even more space efficient algorithm, where we process each sample vertex at a time and record the collisions, thus using a single bit for each node in the graph, as with a Bernoulli process.  {\sc{propagate-s}}, is presented in Algorithm~\ref{SE-MHSE}.
Differently from {\sc{propagate-p}}~ which maintains a signature $s$-array for each vertex $u\in V$, {\sc{propagate-s}}~ uses a $n$-array $\texttt{Sig}[\;]$ that represents the \emph{signature} of the whole graph $G=(V,E)$. More precisely, $\texttt{Sig}[\;]$, at iteration $x_i$ and at each hop $r$, maintains the neighborhood of the seed $x_i$ at distance at most $r$ (line 3, Algorithm \ref{SE-MHSE}).


Although both {\sc{propagate}}-based algorithms have the same asymptotic time complexity, {\sc{propagate-p}}~ is more time-efficient because  the graph  is visited only once for all the sample nodes. The independence of the seeds in {\sc{propagate-s}}~ allows for a very simple implementation of the algorithm in a fully distributed and parallel processing, where cores or machines are coupled with hash functions.  
We only need one final reduction job to collect the whole number of collisions from each core or machine.


When $s=|V|=n$, all {\sc{propagate}}~ algorithms can compute the \emph{exact} average distance, diameter and effective diameter. In this case, {\sc{propagate-p}}~ requires as signature a $n$ bit array for each vertex $u\in V$ thus requiring overall $n^2$ bits, which for large graphs is impracticable. However, {\sc{propagate-s}}~ would require only a $n$-bit array at each iteration. Indeed, {\sc{propagate-s}}~ can be used to compute the \emph{exact} values for various graphs faster than the \texttt{APSP} algorithm implemented in \texttt{WebGraph} \cite{BoVWFI}~(see Section \ref{Sec:tool}). 


On the other hand,  in real applications,  where good approximations are attained even for small values of $s$ (see Theorems~\ref{th:Algo1}, ~\ref{th:Algo2}	and~\ref{th:MHSE-Error}),  then the choice between {\sc{propagate-p}}~ and  {\sc{propagate-s}}~ depends on whether we are in a standalone or a parallel (distributed) setting. 
The above  considerations and Algorithm~\ref{SE-MHSE} lead to the following theorem:

\begin{theorem}
	\label{th:Algo2}
	 {\sc{propagate-s}}~ computes the: diameter, effective diameter, average distance and number of reachable pairs in  $\mathcal{O}(s\cdot\Delta\cdot m)$ time using  $\mathcal{O}(n+m)$ space.
\end{theorem}
\begin{proof}
The proof is essentially analogous to that of Algorithm \ref{MHSE-Bool}. The only difference is on the space complexity. In this case, the algorithm uses a signature of $n$ bits. Thus, the space complexity drops to $\mathcal{O}\left(n+m\right)$.
\end{proof}
\input{./PseudoCodice/SEMHSE-Bool_G.tex}



\paragraph{Error Bounds of the sample size.\label{Section:ErrorBounding}}
We now
evaluate the accuracy of the approximations of the {\sc{propagate}}~ framework.
We use Hoeffding's inequality ~\cite{Hoeffding_1994} to obtain the sample size $s$ for  good approximations  of the average distance,   the effective diameter and the diameter, and  the connectivity rate.



\begin{theorem}
	\label{th:MHSE-Error}
	With  a sample of $s=\Theta\left(\frac{\ln n}{\varepsilon^2}\right)$ nodes, with high probability (at least  $1-\frac{2}{n^2}$), {\sc{propagate}}~ framework ({\sc{propagate-p}}~ and {\sc{propagate-s}}~) compute in time $\mathcal{O}(\frac{\ln n}{\varepsilon^2}\cdot\Delta\cdot m)$:
	\begin{itemize}
		\item [i.]  the average distance with the absolute error bounded by $\varepsilon \frac{\Delta}{\alpha}$  
		\item [ii.] the effective diameter with the absolute error  bounded by  $\frac{\varepsilon} {\alpha}$
		\item [iii.] the diameter with the absolute error bounded by $\frac{\varepsilon} {\alpha}$ 
		\item [iv.] the connectivity rate $\alpha$ with the absolute error bounded by $\varepsilon$ 
	\end{itemize}
where $\alpha$ is the connectivity rate of the graph, and $\varepsilon>0$ a positive constant.
{\sc{propagate-p}}~ and {\sc{propagate-s}}~ requires  $\mathcal{O}\left(n\frac{\log n}{\varepsilon^2}+m\right)$   and   $\mathcal{O}(n+m)$ space  complexity, respectively.
	
\end{theorem}
 \vspace*{-\baselineskip}
\vspace{-0.6mm}
\begin{proof}

	The \emph{average distance} case. Let $X_i=\frac{n\cdot\sum_{u}  d(u,v_i)\cdot R(u,v_i)}{\sum_{u} \sum_{v}  R(u,v)}$ with $\{v_1,\dots, v_{s}\} \subseteq V$ a sample,

	where  $X_i\in [0,\frac{\Delta}{\alpha}]$. The  expectation of $X_i$ is the  average distance:

	\begin{align}
	
		&\textbf{{E}}(X_i)={\sum_{v_i\in V}X_i}\cdot{\textbf{{Pr}}(v_i)
	=\frac{ \sum_{u}\sum_{v_i\in V} d(u,v_i)\cdot R(u,v_i)}{ \sum_{u}\sum_{v_i\in V} R(u,v_i) }
		\label{Eq:average_distance}
	\end{align}
	Then, Hoeffding's inequality \cite{Hoeffding_1994} generates the following bound:
	
	\begin{equation}
	\textbf{{Pr}}\left(\left|\frac{1}{s} \cdot \sum_{i=1}^s ( \textbf{{E}}(X_i)- X_i) \right|\geq \xi\right)\leq 2\cdot\exp\left(\frac{-2s\xi^2\alpha^2}{\Delta^2}\right)
		\label{Hoeffding}
	\end{equation} 
	If $\xi =\varepsilon \frac{\Delta}{\alpha}$ then Equation~\ref{Hoeffding} becomes:
	
	\begin{equation}
		\textbf{{Pr}}\left(\left|\frac{1}{s} \cdot \sum_{i=1}^s ( \textbf{{E}}(X_i)- X_i) \right|\geq \varepsilon \frac{\Delta}{\alpha}\right)\leq 2\cdot\exp\left({-2s\varepsilon^2}\right)
	\end{equation} 
	
	Therefore it is sufficient to take $s=\Theta\left(\frac{\ln n}{\varepsilon^2}\right)$ to have, with high probability (at least   $1-2\cdot\exp\left({-2\ln n}\right)=1-\frac{2}{n^2}$),  an error at most $\varepsilon \frac{\Delta}{\alpha}$.
	
	In a similar way we can derive error bounds for the \emph{effective diameter}. Let $r$ be the effective diameter, and 
	
	\begin{equation}
		X^r_i=\frac{\sum_{\{u: d(u,v_i)\leq r\}}  n\cdot R(u,v_i)} { \sum_{u}\sum_{v} R(u,v) }=\frac{n\cdot|N(v_i,r)|}{|N(\Delta)|}
	\end{equation}
	where  $X_i^r\in [0,\frac{1}{\alpha}]$. Again,  the expectation of the $X^r_i$ is:
	\begin{align}
		\textbf{{E}}(X^r_i)= {\sum_{v_i\in V} X^r_i}\cdot{\textbf{{Pr}}(v_i)}
		=\frac{\sum_{v_i\in V}  |N(v_i,r)| }{|N(\Delta)|}
		=\frac{ |N(r)| }{|N(\Delta)|}


	\end{align}

	Applying  Hoeffding's inequality, with    $\xi =\frac{\varepsilon} {\alpha}$, we  approximate   $\frac{|N(r)|}{|N(\Delta)|}$   by
$\frac{\sum_{i=1}^s X^r_i}{s}=\displaystyle\frac{ n\cdot\sum_{i=1}^s { |N(u,v_i)|}}{s|N(\Delta)|}$
	with a sample of $s=\frac{\ln n}{\varepsilon^2}$ nodes and an   error bound of $\frac{\varepsilon} {\alpha}$, with a high probability of at least $1-\frac{2}{n^2}$. Since the diameter $\Delta$ can be defined in terms of effective diameter $\min_{d'}\left\{d': \frac{ |N(d')|}{|N(\Delta)|}\geq \tau\right\}$ by choosing $\tau = 1$ instead of $0.9$, the effective diameter error bound holds also for the diameter. Finally, we give a bound for the number $|N(\Delta)|$ of \emph{reachable pairs}. Since $|N(\Delta)|$ is a very large number  we give the error bound for the ratio $\alpha= \frac{|N(\Delta)|}{n(n-1)}$. Let us define the random variable
	$
	    X_i^\Delta = \frac{|N(v_i,\Delta)|}{n-1}
	$
	where $X_i^\Delta \in [0,1]$. The expected value of $X_i^\Delta$ is
	\begin{align}
	\textbf{{E}}(X_i^\Delta) 
	\sum_{v_i\in V}\frac{1}{n} \frac{|N(v_i,\Delta)|}{n-1}  = \frac{|N(\Delta)|}{n(n-1)}=\alpha
	\end{align}
	Applying Hoeffding's inequality
	we approximate $\alpha$ with  $s=\frac{\log n}{\varepsilon^2}$ and error bound of $\varepsilon$, with high probability (at least $1-\frac{2}{n^2}$).
\end{proof}




 



\section{Introduction}\label{sec:introduction}

The fast computation of distances between  pairs of nodes in a graph  is a fundamental task in network applications. Distance-based metrics are  also used to compute different notions of centrality for nodes or edges that can be used to detect communities in very large graphs,  as proposed  by Girvan and Newman~\cite{Girvan7821}  or  Fortunato et al.~\cite{Fortunato:2004}.
The \emph{diameter},   i.e.  the maximum distance between all  reachable pairs in a graph, is an important parameter for analyzing  graphs that, for example, change over the time~\cite{Kumar:2006}, or real-world graphs as the web  and social network graphs, which have small diameters~\cite{Kleinberg:2000:SPA} that shrink as  they grow~\cite{Leskovec:2005:GOT}. 
The fastest  exact algorithm for computing the diameter of \emph{sparse graphs}  is based on solving the  All-Pairs Shortest Paths (APSP) problem which, for unweighted graphs, can be computed by executing a Breadth-First Search (BFS) for each vertex, with  a time complexity of $\Omega(mn)$, where $n$ is the number of nodes  and $m$ the number of edges.
For \emph{dense}  graphs, the best algorithm is based on matrix multiplication~\cite{DBLP:journals/jacm/CyganGS15}, which can be performed in time of $\tilde{\mathcal{O}}(n^{\omega})$, where $\omega<2.38$~\cite{COPPERSMITH1990251,Williams12}.
Notice that computing the diameter of a graph with $m$ edges requires $m^{2-o(1)}$ time under the Strong Exponential Time Hypothesis (SETH), which can be prohibitive for very large graphs \cite{Abboud_2014,Dalirrooyfard_2021}, so \emph{efficient approximation algorithms} for diameter are highly desirable.

A trivial $2$-approximation algorithm for the exact diameter in undirected graphs can be computed in $\mathcal{O}(m+n)$ time by means of a BFS-visit starting from an arbitrary node.
A ${3}/{2}$-approximation algorithm was first presented by Aingworth \emph{et al.}~\cite{doi:10.1137/S0097539796303421} with a time complexity of $\tilde{\mathcal{O}}(m\sqrt{n}+n^2)$,  further improved to $\tilde{\mathcal{O}}(m\sqrt{n})$~\cite{DBLP:RodittyW13},  and, with the same approximation ratio,  to  $\tilde{\mathcal{O}}(m^{3/2})$ or $o(n^2)$, depending on the degree of sparsity of the graph~\cite{Chechik:2014:BAA}.



If  a graph is  weakly connected, experiments with real-world graph data sets show that heuristics may boost the average  running time of the diameter computation~\cite{DBLP:journals/tcs/BorassiCHKMT15}.  

The computation of the exact diameter  is however  susceptible to outliers. For this reason,  it is preferable  to use more robust metrics, such as  the \emph{effective diameter}, which is  defined as the a percentile distance between nodes (e.g. $90^{th}$), i.e.  the maximum  distance that allows to connect that percentage of all reachable pairs~\cite{Palmer2001,tauro2001simple}.
For large real graphs, even the exact computation of the  effective diameter  remains prohibitive since  possible approaches  are still based either on solving  APSP or on computing a transitive closure.
Also,  some diameter approximation algorithms~\cite{DBLP:journals/tcs/BorassiCHKMT15,CPPU_2020}  are not applicable  to  the  effective diameter problem, because they are based on  the computation of  the greatest distances from the nodes that do not necessarily pass through all reachable pairs (\cite{DBLP:journals/tcs/BorassiCHKMT15}) or on merging the diameters independently computed on smaller subgraphs  (clusters) (\cite{CPPU_2020}).

An alternative approach  is to compute the \emph{neighborhood function}  to derive  distance metrics. A \emph{neighborhood} $N(u,r)$ is the set of all nodes reachable from the node $u$ by a path of length at most $r$. $N(u,r)$ is also known as the \emph{ball} of center $u$ and radius $r$. Extending this notation, we denote by $N(r)$ the set of all reachable pairs of vertices at distance $r$. 

The most efficient algorithms for approximating the effective diameter are based on the estimate of the size of neighborhoods. For example ANF~\cite{palmer2002anf} is based on BFS and the use of Flajolet-Martin (FM) probabilistic counters~\cite{FlajoletMartin:1985},  and  HyperANF~\cite{Boldi:2011:HAN} is based on the same approach as ANF but with the use of HyperLogLog as probabilistic counter~\cite{DurandFlajolet2003}. 
Cohen~\cite{Cohen:2014:ASR} uses an approach  based on  a non-probabilistic counter, that uses $k$ hash functions  on neighborhoods  by keeping only the minimum hash value (MinHash) for each hash function ($k$-mins sketches). When the hashing values are in the unit interval $[0,1]$, then it is possible to estimate $ |N (u, r )|$ by means of the unbiased cardinality estimator  $\frac{1}{\textrm{MinHash}\left(N(u, r )\right)}$, with the standard error a function  of $k$.
The  MHSE~ framework~\cite{BIGDATA2017}, instead, uses the  MinHash approach to derive  dense representations (\emph{signatures}) of large and sparse graphs that preserve similarity and  thus providing an approximation of the size of the neighborhood  of a node using the Jaccard similarity. 
ANF, HyperANF and MHSE~ are grounded on the observation that  the size of $N(u, r)$ is sufficient to estimate the (effective) diameter.



Basically,   
all these algorithms are based on the execution of a set of BFS-visit one for each node. In particular, they implement  this visit through  dynamic programming by exploiting the property that  the balls $N (u, r)$ are derived, for all $u\in V$ and each $r>0$ , by applying the relation $N (u, r) =  \bigcup _{v: u\rightarrow v} N (v, r-1)$. 
Actually, the union is not exactly computed, but the size of $N (u, r)$  is only estimated  with a probabilistic counter. 
We can similarly evaluate  the \emph{average distance}. 









\subsubsection*{Our contributions}

We propose a \emph{sampling-based} framework to estimate the average distance and  the effective diameter of a given graph $G=(V,E)$,  considering a small set of $s$  sample nodes and  counting the neighbors that contain at least one of these nodes.

This approach leads to {\sc{propagate-p}}~ algorithm  (Algorithm \ref{MHSE-Bool}), which has time complexity $\mathcal{O}\left(m\cdot\Delta\cdots\right)$ and uses $\mathcal{O}\left(s \cdot n +m \right)$ space,  using a bit-like array to keep track of the information. Furthermore, since the algorithm only counts the neighbors that contain nodes from the sample, we can  process each sample node $s_i$, $1\leq i\leq s$, one at time, and derive a linear space $\mathcal{O}(n+m)$
version of the algorithm, namely {\sc{propagate-s}}~ algorithm (see Algorithm \ref{SE-MHSE}). 

We provide an estimate on the sample size needed to achieve a good estimate of the distance metrics up to a small error bound. More precisely,  let $\alpha$ be  the \emph{connectivity rate} of the network. that is  a measure of the the sparseness degree of the  transitive closure of the network, we prove that $s=\Theta(\frac{\log n}{\varepsilon^2})$ sample nodes are sufficient to estimate, with probability at least $1-\frac{2}{n^2}$: 
\begin{enumerate}
    \item the average distance with the error bounded by $\varepsilon \frac{\Delta}{\alpha}$;
    \item both the effective diameter and the diameter with the error bounded by  $\frac{\varepsilon} {\alpha}$;
    \item the connectivity rate $\alpha$ with error bounded by $\varepsilon$.
 \end{enumerate}
From this result we derive that  $\mathcal{O}\left(m \cdot\Delta\cdot\frac{\log n}{\varepsilon^2} \right)$ time is sufficient to obtain a  good approximation with high probability (w.h.p.). 

Finally, unlike already existing algorithms based on probabilistic counters of Flajolet-Martin and Hyper-LogLog used in ANF and HyperANF, our {\sc{propagate}}~ framework provides an \emph{unbiased} estimator with respect to the graph size. 
As experimentally shown, the accuracy of all {\sc{propagate}}~ algorithms is very high even with only $64$ seed nodes, and increases along with their number (see Figure \ref{fig:increment_undirected}). Also, the {\sc{propagate-s}}~ implementation that incrementally (one seed at the time) counts the number of neighbors that contain the sample node can allow the algorithm to stop the execution when the desired precision is achieved. In fact, we can interrupt or continue the computation of the algorithm by observing the confidence interval around the mean of the $s$ results and using their standard deviation or, otherwise we can  expand \emph{progressively}  the sample node set if the stopping criterion is not yet met. 
Although {\sc{propagate-p}}~ and {\sc{propagate-s}}~ have the same asymptotic time complexity, {\sc{propagate-s}}~ is less time-efficient because the graph visit is repeated for each seed node $s_i$. However, the sequential processing of seed nodes in {\sc{propagate-s}}~ allows for a very simple implementation of the algorithm in a fully
parallel/distributed way, where cores or machines are coupled with hash functions and the main operation consists in updating the bit value of the node register (collision). A final reduction job is needed only to collect and sum the full number of collisions from each core or machine. 

	









In Section~\ref{Sec:relatedwork}, we give an overview of relevant results on approximation algorithms of distance based metrics.
In Section~\ref{Sec:algorithm}, we introduce the new algorithms  {\sc{propagate-p}}~ and {\sc{propagate-s}}~ and provide unbiased error bound for the computation of the effective diameter, the diameter, the average distance, and the connectivity rate.
In Section~\ref{Sec:tool}, we report  the experimentation on the effectiveness and the efficiency of these new algorithms. 
In Section\ref{Sec:conclusion}, we conclude and present future research directions.
\section{Preliminaries}
We proceed by formally introducing the terminology and concepts that we use in what follows.
An \emph{undirected graph}\footnote{We use the terms ``graph'' and ``network'' interchangeably.} is an ordered pair $G = (V, E)$, where $V$ is a set whose elements are called \emph{vertices} or \emph{nodes}, and $E$ is a set of \emph{unordered} pairs of vertices, whose elements are called \emph{edges}, or \emph{links} or \emph{arcs}. In a  \emph{directed graph} $G=(V, E)$, $E$ is a set of \emph{ordered} pairs of vertices.
Let $d(u,v)$ be the number of edges in the shortest path between $u$ and $v$.
Given a graph $G=(V,E)$, the \emph{neighborhood at distance at most $r$} for a node $u\in V$ as $N(u,r) = \{v\in V\; :\; d(u,v) \leq r\}$. Alternatively, $N(u,r)$ is the set of $r$-hop neighbors at distance at most $r$ from $u$\footnote{Sometimes, we  use the term ``ball of radius $r$ centered in $u$'' to denote  $N(u,r)$.}.
Additionally, we define the \emph{neighborhood function} at hop $r$ as the size of the set of
pairs of nodes within distance $r$. Formally: $|N(r)| =\left| \{(u,v)\in V\times V \; : \; d(u,v)\leq r\}\right| =\sum_{u\in V}|N(u,r)| $. 

We define the distance metrics of our interest in terms of  the neighborhood function. 
The \emph{diameter} $\Delta$ of a graph is the longest shortest path in the graph. In terms of the neighborhood function we have:
\begin{align}
    \Delta = \min_{r\in \{0,\dots n-1\}}\left\{r : \sum_{u}\left|N(u,r)\right| = \sum_{u}\left|N(u,r+1) \right| \right\}
\end{align}
Similarly, the \emph{effective diameter} is defined as
\begin{align}
    \Delta^{\texttt{eff}} = \min_{r\in \{0,\dots n-1\}}\left\{r : \sum_{u}\left|N(u,r)\right| \geq \uptau\cdot \sum_{u}\left|N(u,\Delta) \right| \right\}
\end{align}
for $\uptau \in [0,1]$. In this work, we consider $\tau = 0.9$, i.e. the $90^{th}$ percentile distance between the nodes. 
We can similarly evaluate the \emph{average distance} of a graph $G=(V,E)$. Let $R(u,v)$ be the reachability function that assumes value $1$ if and only if $u$ can reach $v$ and $0$ otherwise. The average distance can be expressed by means of the neighborhood function as follows:
\begin{align}
\label{eq:avg_distance}
  &\texttt{AvgDist} = \frac{\sum_{u,v\in V}R(u,v)\cdot d(u,v)}{\sum_{u,v}R(u,v)}  =\\
  & \frac{\sum_u \left|N(u,1)\right| + \sum_{u}\sum_{r\in\{2,\dots,\Delta\}} \left(\left|N(u,r)\right|-\left|N(u,r-1)\right|\right)\cdot r}{\sum_u\left|N(u,\Delta)\right|}
\end{align}
Observe that the \emph{number of reachable pairs} can be also defined using the neighborhood function as follows:
\begin{align}
    \texttt{Nr.Reachable Pairs} = \left|N(\Delta)\right|
\end{align}
Finally, we define the \emph{connectivity rate} $\alpha$ of a graph as the sparseness degree of its
transitive closure.
\begin{align}
    \alpha = \frac{\sum_{\substack{u,v\\ u\neq v}}R(u,v)}{n\cdot (n-1)} \in [0,1]
\end{align}
Notice that the more the graph is connected the higher is $\alpha$, and vice versa. As extreme values $\alpha = 1$ for a connected undirected graph, while $\alpha = 0$ when all the vertices are isolated.
\section{Related Works}
\label{Sec:relatedwork}


There are two main approaches to estimate the neighborhood function and, therefore,  the (effective) diameter: \emph{i)} \emph{sampling}:  that is probabilistically drawing a subgraph or more generally a set of nodes by which to exactly compute the (effective) diameter; and, \emph{ii)} \emph{probabilistic}: based on computing the  neighborhood sets   through a suitably  graph traversal  and estimating their sizes using a probabilistic counter. In the following, we  discuss the  methods in more depth.
\paragraph{Estimating Diameter by Sampling\label{SEC::SAMPLING}} 
There are three main   questions  to be addressed  when sampling from large graphs~\cite{Leskovec:2006}: how to  sample nodes and  edges, how to set a  good sample size, how to  evaluate the goodness of the sample, as well as the goodness of the chosen sampling method. 

In the case of undirected and connected graphs, the centrality of nodes can be estimated  by sampling  only  $\mathcal{O}(\frac{\log n}{\varepsilon^2})$ nodes and compute all the distances to all other nodes, with an error of $\varepsilon\Delta$, where $\Delta$ is  the graph diameter~\cite{Eppstein:2001:FAC}, thus reducing the time complexity from $\mathcal{O}\left(n^2\log n +mn\right)$ to $\mathcal{O}(\frac{\log n}{\varepsilon^2}\left (n\log n +m\right))$. 


In the frequent case of graphs changing over time,
two sampling strategies can be applied for testing the goodness of fit: the {\em scale-down}  and {\em back-in-time}, that is, the sample graph $S$ should either  have  similar (scaled-down) properties as compared to the original graph $G$, or  look like the original graph $G$  back at the time when it had the same size of $S$, respectively.
Best performing sampling methods  for the scale-down sampling goal are those based on {\em random walks}, since they are biased towards high degree nodes and provide sampled graphs that are connected. For the back-in-time sampling goal, the {\em PageRank score-based} and  \emph{Forest Fire} type sampling  perform best~\cite{Leskovec:2006}
\paragraph{Estimating Diameter by Probabilistic Counters}

The idea of exploiting the (Flajolet-Martin) FM-counter~\cite{FlajoletMartin:1985} to derive the effective diameter of a graph is to use it to count the number of distinct nodes in each neighborhood $N(u,r)$, for all nodes $u$ and  radius $r$ (the ANF algorithm). For each set $N(u,r)$, ANF yields a concatenation of $l$ bitmasks (\emph{sketches}), each with  the probability of  encountering $1$  at the $i$-th bit  that is equal to $ \frac{1}{2^{i+1}}$. The  $l$ bitmasks are built using  a family of independent hash functions.
An approximation of the number of distinct elements in a stream is derived by averaging the index of the least significant  bit with value $0$ 
in each of the $l$ bitmasks, and is set to $\frac{2^{\textrm{mean}}}{0.77351 }$~\cite{FlajoletMartin:1985}.
Alternatively to the original ANF algorithm,
different types of probabilistic counters may be applied, based on the LogLog and HyperLogLog algorithms~\cite{DurandFlajolet2003,Flajolet07hyperloglog}. Such algorithms are based on modifications of the original Martin-Flajolet algorithm to produce  an improvement over ANF in terms of speed and scalability,  providing a better estimate for the same amount of memory and number of passes.
Although HyperLogLog is the best  approximate data stream counting algorithm,  it is known that it tends to overestimate the real cardinality of small sets~\cite{Heule2013:HPA}. To overcome this inconvenience, an empirical bias correction has been introduced in~\cite{Heule2013:HPA}: the correction works well in a good range of cardinalities, roughly between 18000 and 61000, but errors  persist for much smaller sets. In this case,  the \texttt{LinearCounting} algorithm, introduced in ~\cite{Whang:1990:LPC}, usually provides the best results.

The use of MinHash to estimate the  size of the neighborhood of a node is used in the notion of All Distance Sketch (ADS) of a node of a weighted graph~\cite{Cohen:1997:SFA,Cohen:2014:ASR}.  For each node, an ADS consisting of the first $ k $ MinHash is maintained. The estimate of the neighborhood of a node $u$ is given by hashing the nodes in the interval $[0,1]$ and filtering  a node $v$ when its hash value is less than the $k$-th MinHash of the ADS, and when any other node in ADS is closer to $u$ than to $v$ (is in the  ball $\Phi_{<u}(v)$).
This algorithm  computes; for each pair $(u,v)$, of nodes a distance ({\em closeness similarity}) that generalizes the inverse probability  of the MinHash estimate~\cite{Bar-Yossef2002} with a Jaccard-like similarity function, that is $\frac{1}{max({\pi_{vx}} , {\pi_{ux}})}$ in the case of $k=1$, where $\pi_{u,v}$ is the Dijkstra rank  of $u$ with respect to the node $v$ according to  the position of $u$ by increasing distance from $v$.
The estimate of the Dijkstra rank $\pi_{uv}$ of $u$ with respect to $v$ is  $1+\sum_{j\in ADS(v)\cap \Phi_{<u}(v)}\frac{k}{p_{vj}}$, being $p_{vj}$  the $k$-th value in the ADS list. If the graph is unweighted,  then the BFS visit can be used and Cohen's framework can be considered equivalent in the spirit to HyperANF but with   the use of  the MinCount probabilistic counter  of~\cite{Bar-Yossef2002} instead of HyperLogLog probabilistic counter (we are using here the terminology of~\cite{Heule2013:HPA}). 
However, the implementation of the MinCount counter is very different from the one presented in ~\cite{Bar-Yossef2002}  and does not yield a $O(m)$ space complexity as in ~\cite{Bar-Yossef2002}.

A different probabilistic counter  from \cite{Bar-Yossef2002,Cohen:1997:SFA,Cohen:2014:ASR}  is based on the \emph{MinHash} counter \cite{BIGDATA2017}, which was experimentally shown to be highly  effective in comparison to HyperLogLog based counters.  
A sketching and sampling based technique to model public-private social network graphs proposes  to efficiently preprocess the public graph $G$ and to integrate it with a private user graph node in order to derive graph properties and measures \cite{Chierichetti_2015}. A sketching-based algorithm is proposed to approximate the size of the reachability tree and the size of the private neighborhood at distance $d$ of a node $u$ to within $(1+\varepsilon)$-factor using $\mathcal{O}\left(m\cdot \Delta\cdot \frac{\log n}{\varepsilon^2}\right)$ preprocessing time, $\mathcal{O}\left(n\cdot \frac{\log n}{\varepsilon^2}\right)$ space and $\mathcal{O}\left(|E_u|\cdot \frac{\log n}{\varepsilon^2}\right)$ query time where $\Delta$ is the diameter of the public graph $G$ and $|E_u|$ is the size of the private edge set of node $u$. The authors propose sampling algorithms to approximate the: 1) All-Pairs Shortest Paths (APSP) and within a factor $\mathcal{O}(\log n)$ using preprocessing time $\mathcal{O}(m\cdot \log^2 n)$, space $\mathcal{O}(n \log^2 n)$, and query time $\mathcal{O}(|E_u|\cdot \log^2 n)$; 2) Social Affinity \cite{Panigrahy_2012} between two nodes using the same preprocessing time and space of 1) and  query complexity of $\mathcal{O}(|E_u| + \log^2 m)$; 3) Correlation Clustering within a constant factor when the private graph is a \emph{star} using preprocessing time $\mathcal{O}(m)$, space $\mathcal{O}(m)$, and query time $\mathcal{O}(|E_u| \cdot \log n)$.

	


