Network Topology Inference Using Information Cascades with Limited Statistical Knowledge

We study the problem of inferring network topology from information cascades, in which the amount of time taken for information to diffuse across an edge in the network follows an unknown distribution. Unlike previous studies, which assume knowledge of these distributions, we only require that diffusion along different edges in the network be independent together with limited moment information (e.g., the means). We introduce the concept of a separating vertex set for a graph, which is a set of vertices in which for any two given distinct vertices of the graph, there exists a vertex whose distance to them are different. We show that a necessary condition for reconstructing a tree perfectly using distance information between pairs of vertices is given by the size of an observed separating vertex set. We then propose an algorithm to recover the tree structure using infection times, whose differences have means corresponding to the distance between two vertices. To improve the accuracy of our algorithm, we propose the concept of redundant vertices, which allows us to perform averaging to better estimate the distance between two vertices. Though the theory is developed mainly for tree networks, we demonstrate how the algorithm can be extended heuristically to general graphs. Simulation results suggest that our proposed algorithm performs better than some current state-of-the-art network reconstruction methods.


I. INTRODUCTION
Information is being propagated across networks, such as online social networks, with increasing speed owing to increased network connectivity. There has been recent increased interest to study the spread or diffusion of information, influence, or infections across a network. For example, information dynamics and social learning have been investigated in [1]- [7], most of which assume knowledge of the network structure. Finding the sources of an infection diffusing in a network has been investigated in various works, including [8]- [16]. Most of these efforts again assume that the underlying network structure is known. In many practical applications, knowledge of the network structure may not be readily available, and only the infection times of the nodes may be known. A goal of interest is to infer the network structure based only on this set of infection times, and possibly also limited a priori statistical information or assumptions.
In this paper, we consider the inference of a network topology based on knowledge of the time each vertex in the network receives a piece of information, when an information diffusion is initiated from a known source vertex. More precisely, the network is modeled by an undirected graph G = (V, E), with V the set of vertices and E the set of edges. A source vertex initiates an information diffusion, where the information is spread from an "infected" vertex to its neighbors stochastically along the edges connecting them. The time at which each vertex of G receives the information is observed. We call this the infection time of the vertex, and a collection of infection times with their corresponding source vertex a cascade. We wish to use these information cascades to estimate the connections among vertices of the graph.
The network inference problem has been investigated under various assumptions. For example, [17], [18] considered the inference of directed graphs with a continuous-time diffusion model.
The diffusion along each edge is assumed to be exponential or satisfies a power law. In [19], the authors assumed that the network can be undirected, and, along each edge, information spreads in two steps: a Bernoulli selection step and an exponential transmission step. Other related works based on different diffusion models include [18], [20], [21]. In most of these efforts, knowledge of the probability distribution of information spreading along edges is assumed, and many also assumed the spreading along different edges to be identically distributed. In practice, the spreading distribution is not easy to quantify. For example, information diffusion in an online social network depends on a host of factors [1]. However, moments-such as the average amount of time information takes to diffuse from a vertex to a neighbor-are typically 3 readily estimated from historical data [22], [23]. In this paper, we consider the case where we have limited knowledge of the spreading distribution and require only that the diffusion along different edges be independent. The distribution of information diffusion along edges is unknown to an observer, and only certain moments of the distribution (instead of the full distribution) are given. Therefore, the statistical inference approaches developed in [17]- [20] cannot be applied directly to our problem. Owing to recent advancements in the field of graph signal processing (see [24] for an overview), several network topology inference methods using graph signals have been proposed (for example, [25]- [27]). These approaches are based on the idea that certain graph signals are closely related to eigenvectors of graph-shift operators of a graph (e.g., graph adjacency matrix, graph Laplacian). However, in our setting, the timestamps are related to distance from vertices of a graph to a fixed source node. Such timestamps are usually not directly related to the above mentioned shift-operators, and depend on the choice of the source node. Therefore, the graph signal processing approaches cannot be applied to our problem.
We approach the problem by first determining a necessary condition for perfect tree reconstruction based only on distance information. We introduce the concept of a separating vertex set, denoted by V S , and show that if |V S | is sufficiently large, we can reconstruct the tree using the distances of vertices from those in V S . Because the mean of the infection times are proportional to the distances from a source vertex to other vertices in the graph, we can estimate the distances from the information cascades. We propose an algorithm that makes use of the concept of redundant vertices to reduce the estimation variance. We further extend the method heuristically to general graphs by building on the tree reconstruction algorithm. Such an extension is supported by theoretical results obtained in the paper. The rest of this paper is organized as follows. In Section II, we introduce our graph model and assumptions. In Section III, we introduce the notion of a separating vertex set and derive a necessary condition for perfect tree reconstruction. In Section IV, we introduce the notion of redundant vertices and use that to develop an iterative tree inference algorithm in Section V.
We further extend the algorithm to general graphs in Section VI. Theoretical results supporting the extension are also discussed in Section VI. We present simulation results in Section VII and conclude in Section VIII.

II. GRAPH MODEL
Let G = (V, E) be a connected simple graph (i.e., undirected graph containing no graph loops or multiple edges), with V the set of vertices and E the set of edges. Let d(·, ·) be the length of a shortest path between nodes u and v. We use [u, v] to denote any shortest path between u and v, and (u, v) the path with end vertices u, v excluded. A path P between u and v is called simple if P does not cross itself; thus, [u, v] is always a simple path. For later use, we introduce the following definitions (see Figure 1 for an example). If v is a leaf and the unique neighbor of v is ordinary, then we say that v is a long leaf. The set of long leaves is denoted by L ∂G . Definition 2. We take ∂B G ⊂ B G to be the subset of vertices having a simple path to a leaf without passing through other vertices of B G : Let L ∂B G be the set of vertices v ∈ ∂B G such that none of the neighbors of v are leaves.
Although ∂B G is defined for any graph, it is particularly useful when considering tree networks.
Definition 3. Given a subset of vertices V ⊂ V , the convex hull conv(V ) of V in V is the union of all simple paths connecting any pair of distinct vertices of V .
A cascade c consists of a single source vertex that initiates an information diffusion together with the times each vertex first receives the information. We assume that the information diffusion along different edges is independent with known means. Without loss of generality, we assume that the mean for every edge is µ. We do not require the distributions along different edges to be identical or known.
We assume that each cascade persists long enough to infect all the vertices, and the following information is recorded: Fig. 1. In G, the boundary ∂G consists of the green vertices. The branched vertices BG are the red and yellow nodes, and ∂BG are the yellow nodes. The blue nodes are ordinary. Moreover, v1, v2, and v3 are long leaves, and time of vertex v. We would like to infer the graph structure, by inferring the adjacency matrix For each vertex v, let d v (u) = d(v, u) denote the distance function (from any other node u ∈ G) to v. We have the following simple observation on T c and d v , with v being the source of c.
Proof. For a vertex u ∈ V , because G is a tree, there is a unique simple path P connecting v and The upshot of the lemma is that we can focus on distance functions associated with nodes of the graph.

III. RECONSTRUCTION ACCURACY AND SEPARATING VERTEX SET
We start this section with the following notion of "distance" associated with any subset of vertices of the graph.
By the triangle inequality associated with the usual absolute value, it is easy to verify that d V (·, ·) defines a pseudometric (which means that d V (u, v) can be 0 for u = v) on the set of vertices V of G.
In this section, using d V (·, ·), we aim to develop a necessary condition under which a tree G can be reconstructed uniquely. To this end, we introduce the concept of a separating vertex set as follows (see Figure 2).
. We say that V S is a separating vertex set.
Note that in the above definition, G can be any graph. However, in the case of trees, we have the following result. Proof. Let u, v ∈ conv(V ) be two distinct vertices. By the definition of convex hull, we can find Because G is a tree, there is a unique simple path P Next, we demonstrate how to approximate G using a subset V and the pseudometric d V (·, ·).   (b) Suppose that G is a tree. Let ∂B G contain vertices of ∂B G such that for each v ∈ ∂B G , some neighbors of v are not in conv(V ) (see Figure 4). Moreover, assume that d(u, v) > 1 for u, v ∈ ∂B G ∪ ∂ conv(V ). If V separates G, then E = E, and hence G = G.
(c) In the converse direction, suppose that G is a general graph that does not contain any triangle (three pairwise connected vertices). If E = E, then V separates G. is a simple path if V separates G), which gives a contradiction.
Next, assume that u and v are in different components of G \ conv(V ). Let u 1 and u 2 be their respective closest vertex (projections) on conv(V ). Notice that u 1 , u 2 ∈ ∂B G ∪ ∂ conv(V ).
According to the given condition, d(u 1 , u 2 ) > 1. Without loss of generality, we assume that . Moreover, we have seen in the proof of Lemma 2 that we can choose This contradicts the fact that u and v are connected by an edge in E .
(c) Suppose on the contrary that V does not separate G. We can find two vertices u 1 and u 2 Let u 3 be a vertex connected by an edge to either u 1 or u 2 , Therefore, because E = E , u 3 and u 2 are also connected by an edge. This contradicts the assumption that G does not contain any triangle. The proof is now complete. Motivated by Theorem 1, we introduce the following quantifier to evaluate the effectiveness (using the same notation as in Theorem 1) of a given V .
We have the following observations regarding r.a. based on the definition and results obtained so far. Proof.
(a) Follows immediately from the definition.
(c) From Lemma 2 and noting that ∂B G = ∅ in Theorem 1(b), the result follows.
On the other hand, if G is a tree, it is clear that for two vertices u, v connected by an Moreover, we have the following lower bound regarding the size of V .
Suppose that the following uniqueness property holds true: for any tree G on V with associated Proof. Suppose on the contrary that l < |L ∂G | − |L ∂B G |. By the pigeon-hole principle and Lemma 2, we can always find two simple paths P 1 and P 2 in G \ conv(V ) that are disjoint except where they intersect at a vertex v ∈ B G , and the length of at least one of them, say P 1 , is larger than 1 (see Figure 6).
Moreover, let u 1 be the vertex between u 1 and v. Because both P 1 and P 2 are not in conv(V ), it is impossible to determine if u 1 is connected to u 1 or u 2 based only on the information network (e.g., observing 40% of the network yields on average a r.a.(V ) > 60%). In Section V, we propose an algorithm that does not require a separating vertex set explicitly.

IV. REDUNDANT VERTICES
Our tree inference algorithm is based on the infection times of cascades, whose means are proportional to the distances between vertices. In practice, we face the following problems: (1) owing to the stochastic nature of the diffusion process, the recorded infection times at various vertices are not exactly proportional to the distance to the source; (2) infection times provided by cascades starting at certain vertices may be redundant when considered together with timestamps given by cascades starting at other vertices. In this section, we introduce and discuss the concept of redundant vertices before presenting a method to mitigate the aforementioned shortcomings in our tree inference algorithm in Section V.
We remark that here E is assumed to be constructed using d V (u, v) ≤ 1 in Definition 6, so that some results are more general. When necessary, we may also use the condition d V (u, v) = 1 instead, in which case we will state this explicitly.
Intuitively, when two vertices are mutually replaceable, they give the same amount of information in the reconstruction task. From the definition, we have the following simple observations.
Therefore, v i is redundant if and only if they are not connected to each when we use V \{v i }; (b) This follows immediately from the criterion given in (1).
(c) According to the definition, E constructed from V \{v 1 } and V \{v 2 } are both the same as that constructed from V . T v u be the subtree rooted at u.
be their respective closest points in conv(V \ {v i }). We have seen that we can always find Without loss of generality, we assume that u ∈ Suppose that d(u , v ) > 1 and without loss of generality that d(u, u ) ≤ d(v, v ). Therefore, For the remaining case where d(u , v ) ≤ 1, we treat (a) and (b) separately.
(a) Suppose that d(u , v ) ≤ 1 and v i = v i . Without loss of generality, we can further assume In this case, we see that (b) If both u and v are different from v i , then the same argument as above does the job because, in this case, Figure 8).
By the definition of convex hull and the choice of Notice that P contains ordinary vertices. Therefore, the assumption asserts that there is a It is easy to verify that Using the previous proposition, we can prove the following corollary.
Corollary 3. Suppose that G is a tree. Let ∂B G be any subset of ∂B G such that the distance between any two vertices of ∂B G is at least 2. Moreover, if each element of ∂B G has at most two non-leaf neighbors, then any V contains a subset V of size at most |∂G| − |∂B G | (which is a constant that depends only on G) such that all the vertices not in V are redundant w.r.t.
Proof. Let T be the convex hull of V and L the leaves of T . For each u ∈ ∂B G ∩ T , we define the set L u ⊂ L as follows: In other words, L u consists of the leaves of T to whom u is the closest among all the members If a neighbor v of u is not a leaf, then let l u be the (unique) node in L u such that v ∈ [l u , u]; and otherwise, let l u be any node in L u . Form V by removing these l u from V (see Figure 9). It is clear that |V | ≤ |∂G| − |∂B G |. Moreover, each other vertex is redundant by Proposition 1(a) and (b). Simulation results on randomly generated trees with 500 nodes show that on average, the bound |∂G| − |∂B G | given in Corollary 3 is at most 32% of |V |.
Proposition 1 should be modified if G is a general graph. To be more precise, in addition to the given condition, we have to assume further that v i is not contained in a cycle (see Figure 10 for a counterexample). Because v 1 and v 2 are connected by a direct edge, without loss of generality, we can assume In the following cases, we can also conclude that v 1 is redundant: (1) Either (a) or (b) of Proposition 1 holds for v 2 . Notice that we always have that v 1 is either v 1 or v 2 .
(2) If we construct E using To see this, suppose that u and v are not connected by an edge using v 1 , but are connected by an edge using v 2 . This can only happen when The same argument as the the proof of Proposition 1 (use a neighbor of v 2 in place of v in the last two paragraphs; and see Figure 11 for an illustration) proves the claim.
If any of the above cases happens, and information diffusion happens deterministically, v 1 and v 2 are mutually replaceable w.r.t. V in inferring the structure of the graph. Simulation results show that if |V | ≥ 0.3|V |, then on average, more than 84% of pairs of V connected by a direct edge are mutually replaceable. In practice, the diffusion process is stochastic. Time information provided by v 1 (respectively, v 2 ) can be used to average out the time information at v 2 (respectively, v 1 ) to obtain a better estimate of the distance with a lower variance. We first discuss the reconstruction step. For u, v ∈ V , from Theorem 1 and Remark 1, to determine if u, v are connected by an edge, we want to compare This motivates us to introduce the following: Here, we take the average difference with 1 instead of using sup as in Definition 4. This is because when the timestamps are stochastically generated, taking sup is sensitive to change of variance of distributions. Essentially, this is nothing but replacing the L ∞ pseudometric by the L 1 pseudometric.
If W (u, v) is small, it suggests a higher chance that u, v are connected by a direct edge. We call W the weight matrix, and its entries the weights. If we want to infer the structure of a tree of size n, we can select n − 1 (total number of edges) pairs of distinct vertices (u, v) such that In doing so, we obtain an estimated graph G = (V, E ). We can directly use E for the selection step. An alternative is to use the weight matrix W for the job. More precisely, we can set a numerical condition C based on W , and select a pair (u, v) as long as satisfies the pre-set condition C. For example, for a fixed parameter k, we can choose kn pairs of (u, v) with the smallest W (u, v) value. This reflects our belief that each selected (u, v) has a "high chance" of being connected by an edge.
For a selected pair of vertices (v i , v j ) with v i , v j ∈ V and u ∈ V , we construct the times at v j using T v i in the transfer step as follows: for each u ∈ V , We can now update T v j (·) by its average with T v i v j (·). Once T v j (·) are updated for every v j ∈ V , we can repeat the reconstruction step.
We summarize the above discussion in as our Iterative Tree Inference (ITI) algorithm in Algorithm 1.

VI. THE CASE OF GENERAL GRAPHS
In this section, we consider general simple graphs. We first discuss theoretical results on information propagation on general graphs, which lend support to our heuristic extension of the ITI algorithm. We then propose a general graph inference algorithm.
We assume that G is undirected, and the information propagation along every edge of G is independently distributed according to an unknown continuous distribution with probability for Each pair of (v i , v j ) selected do 6: Generate new cascades T v j v i (·) and T v i v j (·) as in (2).

7:
Update density function (pdf) f with mean µ. We also assume that f has infinite support. The continuous distributions commonly used in the literature to model diffusions (for example, [17], [18]) satisfy this assumption.
As a notational convention, we use a lower-case letter (e.g., f ) to denote the pdf of a continuous probability distribution, and the corresponding capital letter (e.g., F ) for its cumulative distribution function (cdf). Moreover, we letF = 1 − F .

A. Theoretical observations
Let u, v be two distinct vertices of a graph G. We use X u,v to denote the random variable Lemma 4. Let m, n, k be positive integers. Then for some x ∈ (0, 1), we have We find immediately that h (1) = −1/k < 0. As h (x) is continuous in a small neighborhood Proof: It suffices to prove thatF =F u,v . Suppose that the contrary is true. If u and v is connected by an edge, the mean propagation time will be strictly smaller than that of f as we assume f has infinite support (a more general result is given in Lemma 5 below). For the rest of the proof, we assume (u, v) / ∈ E. We first reduce the graph G to a simpler graph (see Figure 12 for illustration). Construct G 1 as follows: if both end points of an edge e in G are different from u and v, then shrink e to a single point (take note that this is different from removing e) in G 1 . As u, v are not connected by an edge in G, each path between u and v is of length 2 in G 1 . We should take note that multiple edges are allowed between two nodes in G 1 (and G 2 constructed below). The shrinking process reduces the time to travel from u to v and henceF u,v ≥F 1 .
Let C be a connected component of G 1 \{u, v}. It is easy to see that C is made up of a single node v C , with m C paths connecting v C to u, and n C paths connecting v C to v. Denote the total number of connected components of G 1 \{u, v} by k. Define m = max C {m C } and n = max C {n C }. Construct G 2 as follows: for each C, we add m − m C edges between v C and u, and add n − n C edges between v C and v. As we add additional edges between nodes without changing the rest of the graph, we haveF 1 ≥F 2 . The number of connected components of BecauseF (t) is continuous,F (0) = 1 and lim t→∞F (t) = 0. By the intermediate value theorem, (0, 1] is contained in the image ofF . Therefore, from Lemma 4, we obtain a contradiction and the theorem is proved. Theorem 2 suggests that even if the mean propagation time (as was used in the ITI algorithm) for X u,v is similar to that of a single edge, we can use higher moments to determine if u and v are connected by a single edge (except for certain pathological distributions that share the same moments). In the following, we provide bounds on the moments of X u,v to guide us in our extension of the ITI algorithm to general graphs.

Lemma 5.
Suppose that (u, v) ∈ E. Consider the graph G in which (u, v) is removed, and suppose that G is connected. Let Y u,v be the propagation time from u to v in G and its pdf be h. Then for all k ≥ 1, and any 0 > 1 > 0, where the interchange of integration in the third equality follows from Tonelli's theorem. The lemma is proved.
In particular, by choosing 0 − 1 to be sufficiently large and noting thatH(·) > 0 (as h has infinite support), Lemma 5 implies that E Y k u,v > E X k u,v for all k ≥ 1. Moreover, if the graph G is not too dense in the sense that F (1)H(1) is suitably large, then the difference between the means of Y k u,v (without an edge between u and v) and X k u,v (with an edge between u and v) can be made suitably large by choosing a sufficiently large k. This allows us to determine if (u, v) ∈ E based on empirical observations of the propagation times raised to the k-th power.
However, we may not observe information cascades from every vertex u in the network, and typically have to rely on information cascades starting at sources other than u and v. We have the following bound relating the propagation times to u and v from a distinct source node. Lemma 6. Let G u,v be the union of all the simple paths connecting u, v (i.e., the convex hull, according to Definition 3) in G; and w ∈ G. Then for any k ≥ 1, Proof: For any vertices a, b, let P a,b be the path associated with X a,b . The concatenation of P u,w and P u,v is a path from w to v with possibly some edges repeated. We therefore have almost surely, Similarly, X w,u − X w,v ≤ X u,v almost surely. We then obtain where the first inequality follows from Jensen's inequality, and the lemma is proved.
using T w (u) and the transfer step in the ITI algorithm in Section V). The reverse implication is not necessarily true, but for algorithmic convenience, the lemma suggests that we use an empirical estimate of the latter term as a proxy for E X k u,v .

B. Discussions and implications
We now discuss some implications of the results obtained in Section VI-A. Consider any pair of distinct nodes u, v, and the following cases: (i) Suppose that the number of paths between u and v is small (i.e., the graph G is sparse). (ii) Suppose that the number of paths between u and v is large (i.e., the graph G is dense).
According to Lemma 5 and the discussions thereafter, the existence of an edge between u and v can make both the sample mean and higher moments small relative to the corresponding moment values if such an edge is missing. Therefore, in this case, we may choose to infer that the edge (u, v) exists based on the size of the sample mean and higher moments. However, we should mention that if there are too many paths between u and v, then in practice, any distribution-based estimation is prone to errors as demonstrated in the discussion and example below.
Our next example demonstrates that it is almost impossible to determine if there exists an edge (u, v) in the graph G if it is very dense. To show this, we need the following result.
Lemma 7. Suppose that X and Y are two continuous random variables on (0, ∞), with cdf P and H respectively. Let Z = min{X, Y }. Then the total variation distance between the distributions of Y and Z is bounded from above by inf >0 {H( ) + P ( )}.
Proof: Let p and h be the pdf of P and H respectively. It is easy to show that the pdf of the distribution associated with Z is p(1 − H) + h(1 − P ). Therefore, we have to show that for To see this, we first apply the triangle inequality: The two integrals on the right hand side of (3) can be bounded separately as: The result follows by adding up the two inequalities.
Example 2. Suppose that the propagation along each edge are i.i.d. with exponential distribution having mean 1. Then, we have F (x) = 1 − e −x . Assume that there are k independent paths of length l between two distinct nodes u and v, which are not connected by an edge. Along each path, the propagation follows a Gamma distribution Γ(l, 1), whose cdf is 1 − e −x l−1 i=0 x i /i!. Let Y be the propagation time between u and v. Then, it can be shown that its complementary Let Z be the propagation time from u to v if the edge (u, v) is added to the graph. By Lemma 7, the total variation distance between Y and Z is bounded from above by We have lim →0 + (1−e ) = 0. On the other hand, the derivative of e −x l−1 i=0 we can always choose small enough and k large enough such that the upper bound (4) is as close to 0 as we wish. This suggests that in practice, if there are many paths between the two nodes, then it is almost impossible to determine if there is an edge between them or not by any distribution-based method.

C. The graph inference algorithm
The discussion in Section VI-B can be summarized in the following dichotomy: when the graph is sparse (as measured by the edge to vertex ratio, for example) or the distributions of the propagation times along each edge have small variance, it is enough to use the mean of the distributions as in the case of trees. On the other hand, if the graph is highly connected, the existence of an edge between two vertices u and v can make the mean propagation time between u and v small relative to µ. Therefore, it is instructive to use the length of the propagation time between u and v to decide if they are connected by an edge or not. The same consideration applies to other moments (as compared against unbiased sample moments); and they can be used as additional criteria to decide the existence of edges.
In a general graph, it is usually unknown whether the connection between two vertices u and v is dense or sparse. One way to overcome such a difficulty is to compute the difference between the sample mean (respectively, sample moments) with both the theoretical mean (respectively, theoretical moments) as well as 0. Once these two values are obtained, it is enough to take the smaller one. Hence the weight matrix being used in ITI should be modified based on available moment information. Suppose that the mean µ and variance σ 2 of propagation time along edges are known. We define the following: where "ave" is used to denote average over v i ∈ V as in (1) to shorten the expressions; and In the case of general graphs, we usually do not know the total number of edges based on the number of vertices n, in contrast to tree networks. Therefore, we first randomly choose a small percent of vertices and find their average degree deg s . We take deg s to be an estimate of the actual average degree of the network; and estimate the total number of edges as n e = n · deg s .
Based on these, we propose below the Graph Inference (GI) algorithm (Algorithm 2) as a heuristic extension of ITI.
A possible generalization of Algorithm 2 if higher order moments are available is to modify W 1 , W 2 and hence W accordingly as follows. According to Lemma 6 and the discussion thereafter, we may use |T v i (u) − T v i (v)| to estimate the sample moments. For each k ≥ 1, the k-th sample moment is denoted by S The k-th moment of the distribution (of propagation time) along each edge is denoted by µ k .
We fix a finite set of m positive numbers: {k 1 = 1, k 2 , . . . , k m }; and a continuous m-variable function φ. Define for each 1 ≤ i ≤ m: Under this generalization, the procedure depicted in Algorithm 2 uses m = 2, k 1 = 1, and k 2 = 2, while φ is the averaging function. The choice of φ should reflect one's belief about which moment should play a more important role in the network inference task. for Each pair of (v i , v j ) selected do 6: (2). 7: Update

VII. SIMULATION RESULTS
In this section, we present simulation results to verify the performance of our proposed topology inference algorithms. We first apply our ITI algorithm on tree networks, and compare its performance with with the tree reconstruction (TR) algorithm proposed in [19], which is most similar to ours in assumptions. We then perform simulations on general graphs, including some real-world networks, and compare the performance of the GI algorithm with the the NetRate algorithm proposed in [18]. As the NetRate algorithm assumes knowledge of the diffusion distribution, we also study the performance impact when there is a mismatch between the assumed and actual distributions.
Suppose that A G is the true adjacency matrix of G and A is an estimated adjacency matrix.
To evaluate the performance of our method, we define the edge recovery rate as For the same number of edges, each mistake in identifying an edge causes a mistake at another pair of vertices. To account for this, we have a factor of 2 in the denominator; and this makes R a real number in [0, 1]. The term 1 − R is called the error rate, in which both undetected edges and false positives are taken into account.

A. Tree networks
In this subsection, we show and discuss simulation results to verify the performance of our proposed algorithm for tree networks. As we are considering tree networks, in the reconstruction step, we always have |E| = n − 1 edges, where n is the number of vertices.
In each simulation run, we randomly generate trees with n = 500 vertices. We then randomly choose n c distinct sources, and generate κ v cascades per source using independent exponential spreading with mean µ = 1 at each edge. In applications, κ v can be different for distinct nodes v; however, in our simulations below, we keep it constant for all v for simplicity. We apply the ITI algorithm, and evaluate the performance by using (7).
We first study the edge recovery rate by varying n c and κ v , and skip the selection and transfer steps by setting I = 0 (see Figure 13). We notice that κ v has a significant impact on the performance. If the number of cascades per source κ v is small, the performance can be greatly improved if we perform additional transfer steps (see Figures 14). These results demonstrate the usefulness of the theory developed in Section IV. The choice I = 2 is usually enough, and the number of edges m s in the selection step can be chosen between n and 1.5n.
Moreover, comparing the curves for n c /n = 0.3, κ v = 2 and n c /n = 0.5, κ v = 1, we see that the performance is improved if we have more cascades originating from the same source. This suggests that the averaging process allows a better approximation of the distance on a tree.
Finally, we compare our method with the TR algorithm proposed in [19]. Although the theoretical part of [19] assumes i.i.d. exponential distribution for propagation time along different edges, the TR algorithm itself requires n and {T v i } as the only input. The comparison is shown in Figures 15 and 16. In Figure 16, we test the effect of having different diffusion distributions for different edges. The distributions are randomly selected unknown Gamma distributions with the same mean. As shown from the plots, our method performs much better in all the cases because our method does not require identical distributions for propagation times along different edges.

B. General graphs
For general graphs, we compare our GI algorithm with the NetRate algorithm proposed in [18]. 1 Although NetRate works under a completely different set of assumptions (in particular, [18] assumes propagation along edges follows one of the following families of distributions: exponential, power-law, or Rayleigh), it proves to be very powerful in graph topology inference using cascade information.
To accommodate comparison with NetRate, we use the standard exponential distribution with rate 1/µ = 1 for propagation time along each edge. We compare the performance of NetRate and GI on Erdös-Rényi graphs, the Forest-fire network [28], and a real-world Email network [28]. The parameters of all networks are described in the plots.
From the plots (Figures 17, 18, 19, and 20), we see that our method performs better in all the tested cases if the number of cascades does not exceed 60% of the number of nodes. However, we should mention that if the ratio is closer to 1 (i.e., on average each node sends a cascade), then NetRate can have a better performance for certain graph types (Figures 17 and 19). On the other hand, for ER-graphs with large average degree and the Email network, GI performs better for the entire spectrum of n c /n from 10% to 100%. The GI algorithm has a noticeably better performance when n c /n is very small, as compared with NetRate. For example, in the case of the Email Network and n c /n = 10%, NetRate has less than 5% edge recovery while the GI has more than 27% edge recovery. We note that since the Email network is dense, all inference methods based on the assumption that diffusion across each edge follows a distribution will have limited performance (cf. Example 2).
We would like to point out another important advantage of our method. Because of the nature of the two algorithms, our method is computationally much more efficient. For example, using the same computational resource under the same simulation settings, the time used to run GI and NetRate is a few seconds versus a few hours. Therefore, our method is more suitable in time-critical applications when computational resource is limited.

C. Distribution mismatch
For the next set of simulations, we test the effect of distribution mismatch on NetRate. To be precise, as our algorithm does not require knowledge of the type of distribution governing the diffusion process while NetRate does, we want to test whether such prior knowledge is crucial to NetRate.
The setup of the simulations is as follows: on each type of network, we generate the cascades using the exponential distribution with rate 1. We run the NetRate algorithm with the incorrect distributions: either the power-law distribution (POW) or the Rayleigh distribution (RAY), as  these are the other two families of distributions discussed in [18]. The results are shown in the same Figures 17, 18, 19, and 20, by dashed curves.  From the plots, we see that the performance of NetRate drops significantly if there is a distribution mismatch. For example, if the power-law distribution is used, the edge recovery of NetRate is close to 0% regardless of n c /n and the network type.
The experiments suggest that prior knowledge of the diffusion distribution is important to guarantee the performance of NetRate. In contrast, for the GI algorithm, no such prior knowledge is required.

VIII. CONCLUSION
In this paper, we have developed a theory and method for graph topology inference using information cascades and knowledge of some moments of the diffusion distribution across each edge, instead of the distribution itself. In the case of tree networks, we provided a necessary condition for perfect reconstruction, and used the concept of redundant vertices to propose an iterative tree inference algorithm. Our method works well as long as the total number of cascades is not too small compared to the size of the network. Moreover, our method works better if there are more cascades at each chosen source. Simulations demonstrate that our method outperforms the tree reconstruction algorithm in [19]. We have also provided some theoretical insights into how the moments of the propagation time between two vertices in a general graph behave, and extended our tree inference method heuristically to general graphs. Our simulation results suggest that our graph inference algorithm performs reasonably well, if the total number of cascades is not too small compared to the size of the network, and often outperforms the NetRate algorithm in [18]. Moreover, our method is suitable for time-critical applications owing to its low complexity.