## 2 Materials and Methods
### Online Network Topology Inference
#### 2.2.1 Algorithm Construction
## 3 Results

Here we assess the performance of the proposed algorithms in recovering sparse real-world graphs. To that end, we: (i) illustrate the scalability of Algorithm 1 using a relatively large-scale Facebook graph with thousands of nodes in a batch setup; (ii) evaluate the performance of the proposed online Algorithm 2 in settings with streaming signals; and (iii) demonstrate the effectiveness of Algorithm 2 in adapting to the dynamical behavior of the network. Throughout this section, we infer unweighted real-world networks from the observation of diffusion processes that are synthetically generated via graph filtering as in (2). For the graph shift \(\mathbf{S}=\mathbf{A}\), the adjacency matrix of the sought network, we consider a second-order filter \(\mathbf{H}=\sum_{l=0}^{2}h_{l}\mathbf{S}^{l}\), where the coefficients \(\{h_{l}\}\) are drawn uniformly from \([0,1]\). To measure the edge-support recovery, we compute the F-measure defined as the harmonic mean of edge precision and recall (precision is the percentage of correct edges in \(\hat{\mathbf{S}}\), and recall is the fraction of edges in \(\mathbf{S}\) that are retrieved). ### Facebook Friendship Graph: Batch

To evaluate the scalability of Algorithm 1, consider a directed network of \(N=2888\) Facebook users, where the 2981 edges represent friendships among the users [50; 51]. More precisely, an edge from node \(i\) to node \(j\) exists if user \(i\) is a friend of the user \(j\). To make the graph amenable to our framework, we assume that the friendships are bilateral and ignore the directions. First, we notice that \(\operatorname{rank}(\mathbf{W}_{\mathcal{D}})=2882\) (cf. Proposition 1). This means that knowing the GSO's eigenvectors and \(k=6\) suitably chosen edges as a priori information would lead to a singleton feasibility set. To test Algorithm 1 in recovering this reasonably large-scale graph, the performance is averaged over 10 experiments wherein we assume that we know the existence of \(|\Omega|=5\) randomly sampled edges in each experiment. We then generate \(T=10^{3}\), \(10^{4}\), \(10^{5}\), or \(10^{6}\) synthetic random signals \(\{\mathbf{y}_{t}\}_{t=1}^{T}\) adhering to generative diffusion process in (2), where the entries of the inputs \(\{\mathbf{x}_{t}\}_{t=1}^{T}\) are drawn independently from the standard Gaussian distribution to yield stationary observations. We obtain \(\hat{\mathbf{C}}_{\mathbf{y}}\) via a sample covariance estimate. For the aforementioned different values of \(T\), the recovered \(\hat{\mathbf{S}}\) obtained after running Algorithm 1 results in the following F-measures. \begin{tabular}{c c c c c} Number of observations (\(T\)) & \(10^{3}\) & \(10^{4}\) & \(10^{5}\) & \(10^{6}\) \\ \hline \hline F-measure & 0.45 & 0.77 & 0.87 & 0.94 \\ \end{tabular} 

As the number of observations increases, the estimate \(\hat{\mathbf{C}}_{\mathbf{y}}\) becomes more reliable which leads to a better performance in recovering the underlying GSO; recall that perfect support recovery corresponds to an F-measure of 1. This is visually apparent from Figure 1, where we depict the ground-truth Facebook network along with the estimated graphs for \(T=10^{4}\), \(10^{5}\), and \(10^{6}\). Moreover, the reported results corroborate the effectiveness of Algorithm 1 in recovering large-scale graphs. Off-the-shelf algorithms utilized to solve related topology inference problems in [6] are not effective for graphs with more than a few hundred nodes. Figure 1: Recovery of Facebook friendship graph with \(N=2882\) nodes. Adjacency matrix of (**a**) ground-truth network; and estimates for (**b**) \(T=10^{4}\); (**c**) \(T=10^{5}\); and (**d**) \(T=10^{6}\). It is apparent how recovery performance markedly improves as the sample size increases; see also the accompanying table with the corresponding F-measure values. ### Zachary's Karate Club: Online

Next, we consider the social network of [PERSON]'s karate club ((1), Ch.