 |
Center for Nonlinear Studies |
As networks grow in size and complexity, it becomes increasingly more important to analyze them efficiently. Motivated by this, we have developed several new statistics for characterizing various network properties. These statistics are based upon what we call ``Perimetric'' edges, edges where both nodes are the same distance from a source node, and are related to quantities such as the number of odd cycles in the graph. Finding perimetric edges is inexpensive, scaling linearly with the number of edges in the graph. This allows for fast and accurate characterization of the full network using only a fraction of the available edges. Properties of these statistics are studied, both analytically and numerically. Some possible applications are explored, including how to characterize the ``efficiency'' of the network and how to use these statistics to estimate how close the network is to being bipartite. This measure of bipartivity is easier to implement and cheaper to compute than existing methods.