This paper introduces a novel algorithm for cardinality, i.e., the number of nodes, estimation in large scale anonymous graphs using statistical inference methods. Applications of this work include estimating the number of sensor devices, online social users, active protein cells, etc. In anonymous graphs, each node possesses little or non-existing information on the network topology. In particular, this paper assumes that each node only knows its unique identifier. The aim is to estimate the cardinality of the graph and the neighbours of each node by querying a small portion of them. While the former allows the design of more efficient coding schemes for the network, the second provides a reliable way for routing packets. As a reference for comparison, this work considers the Best Linear Unbiased Estimators (BLUE). For dense graphs and specific running times, the proposed algorithm produces a cardinality estimate proportional to the BLUE. Furthermore, for an arbitrary number of iterations, the estimate converges to the BLUE as the number of queried nodes tends to the total number of nodes in the network. Simulation results confirm the theoretical results by revealing that, for a moderate running time, asking a small group of nodes is sufficient to perform an estimation of 95 of the whole network.
While the authors in @cite_14 propose a model for distributed cardinality estimation in anonymous networks using statistical inference methods, the authors in @cite_11 present a scheme for estimating the number of reachable neighbours for a given node and a size of the transitive closure. They present an @math time complexity algorithm based on Monte Carlo that estimates, with a small error, the sizes of all reachability sets and the transitive closure of a graph.
@cite_14 @cite_11
2021468256 1965996575
Computing the transitive closure in directed graphs is a fundamental graph problem. We consider the more restricted problem of computing the number of nodes reachable from every node and the size of the transitive closure. The fastest known transitive closure algorithms run inO(min mn,n2.38 ) time, wherenis the number of nodes andmthe number of edges in the graph. We present anO(m) time randomized (Monte Carlo) algorithm that estimates, with small relative error, the sizes of all reachability sets and the transitive closure. Another ramification of our estimation scheme is a O(m) time algorithm for estimating sizes of neighborhoods in directed graphs with nonnegative edge lengths. Our size-estimation algorithms are much faster than performing the respective explicit computations. This paper presents an efficient fully dynamic graph algorithm for maintaining the transitive closure of a directed graph. The algorithm updates the adjacency matrix of the transitive closure with each update to the graph; hence, each reachability query of the form "Is there a directed path from i to j?" can be answered in O(1) time. The algorithm is randomized and has a one-sided error; it is correct when answering yes, but has O(1 nc) probability of error when answering no, for any constant c. In acyclic graphs, worst case update time is O(n2). In general graphs, the update time is O(n2.26). The space complexity of the algorithm is O(n2). We apply adjacency matrix clustering to network attack graphs for attack correlation, prediction, and hypothesizing. We self-multiply the clustered adjacency matrices to show attacker reachability across the network for a given number of attack steps, culminating in transitive closure for attack prediction over all possible number of steps. This reachability analysis provides a concise summary of the impact of network configuration changes on the attack graph. Using our framework, we also place intrusion alarms in the context of vulnerability-based attack graphs, so that false alarms become apparent and missed detections can be inferred. We introduce a graphical technique that shows multiple-step attacks by matching rows and columns of the clustered adjacency matrix. This allows attack impact responses to be identified and prioritized according to the number of attack steps to victim machines, and allows attack origins to be determined. Our techniques have quadratic complexity in the size of the attack graph The primary purpose of a network is to provide reachability between applications running on end hosts. In this paper, we describe how to compute the reachability a network provides from a snapshot of the configuration state from each of the routers. Our primary contribution is the precise definition of the potential reachability of a network and a substantial simplification of the problem through a unified modeling of packet filters and routing protocols. In the end, we reduce a complex, important practical problem to computing the transitive closure to set union and intersection operations on reachability set representations. We then extend our algorithm to model the influence of packet transformations (e.g., by NATs or ToS remapping) along the path. Our technique for static analysis of network reachability is valuable for verifying the intent of the network designer, troubleshooting reachability problems, and performing "what-if" analysis of failure scenarios.