Why do simple algorithms for triangle enumeration work in the real world?.
Abstract Not Provided
Engineering topics
Publications and source records attributed to Wilson, Alyson G.
Abstract Not Provided
Explore the source record for details and available documents.
Enumerating triangles (3-cycles) in graphs is a kernel operation for social network analysis. For example, many community detection methods depend upon finding common neighbors of two related entities. We consider Cohen's simple and elegant solution for listing triangles: give each node a 'bucket.' Place each edge into the bucket of its endpoint of lowest degree, breaking ties consistently. Each node then checks each pair of edges in its bucket, testing for the adjacency that would complete that triangle. Cohen presents an informal argument that his algorithm should run well on real graphs. We formalize this argument by providing an analysis for the expected running time on a class of random graphs, including power law graphs. We consider a rigorously defined method for generating a random simple graph, the erased configuration model (ECM). In the ECM each node draws a degree independently from a marginal degree distribution, endpoints pair randomly, and we erase self loops and multiedges. If the marginal degree distribution has a finite second moment, it follows immediately that Cohen's algorithm runs in expected linear time. Furthermore, it can still run in expected linear time even when the degree distribution has such a heavy tail that the second moment is not finite. We prove that Cohen's algorithm runs in expected linear time when the marginal degree distribution has finite 4/3 moment and no vertex has degree larger than {radical}n. In fact we give the precise asymptotic value of the expected number of edge pairs per bucket. A finite 4/3 moment is required; if it is unbounded, then so is the number of pairs. The marginal degree distribution of a power law graph has bounded 4/3 moment when its exponent {alpha} is more than 7/3. Thus for this class of power law graphs, with degree at most {radical}n, Cohen's algorithm runs in expected linear time. This is precisely the value of {alpha} for which the clustering coefficient tends to zero asymptotically, and it is in the range that is relevant for the degree distribution of the World-Wide Web.
This paper develops Classical and Bayesian methods for quantifying the uncertainty in reliability for a system of mixed series and parallel components for which both go/no-go and variables data are available. Classical methods focus on uncertainty due to sampling error. Bayesian methods can explore both sampling error and other knowledge-based uncertainties. To date, the reliability community has focused on qualitative statements about uncertainty because there was no consensus on how to quantify them. This paper provides a proof of concept that workable, meaningful quantification methods can be constructed. In addition, the application of the methods demonstrated that the results from the two fundamentally different approaches can be quite comparable. In both approaches, results are sensitive to the details of how one handles components for which no failures have been seen in relatively few tests.
Both the U. S. Department of Defense (DoD) and Department of Energy (DOE) maintain weapons stockpiles: items like bullets, missiles and bombs that have already been produced and are being stored until needed. Ideally, these stockpiles maintain high reliability over time. To assess reliability, a surveillance program is implemented, where units are periodically removed from the stockpile and tested. The most definitive tests typically destroy the weapons so a given unit is tested only once. Surveillance managers need to decide how many units should be tested, how often they should be tested, what tests should be done, and how the resulting data are used to estimate the stockpile's current and future reliability. These issues are particularly critical from a planning perspective: given what has already been observed and our understanding of the mechanisms of stockpile aging, what is an appropriate and cost-effective surveillance program? Surveillance programs are costly, broad, and deep, especially in the DOE, where the US nuclear weapons surveillance program must 'ensure, through various tests, that the reliability of nuclear weapons is maintained' in the absence of full-system testing (General Accounting Office, 1996). The DOE program consists primarily of three types of tests: nonnuclear flight tests, that involve the actual dropping or launching of a weapon from which the nuclear components have been removed; and nonnuclear and nuclear systems laboratory tests, which detect defects due to aging, manufacturing, and design of the nonnuclear and nuclear portions of the weapons. Fully integrated analysis of the suite of nuclear weapons surveillance data is an ongoing area of research (Wilson et al., 2007). This paper introduces a simple model that captures high-level features of stockpile reliability over time and can be used to answer broad policy questions about surveillance programs. Our intention is to provide a framework that generates tractable answers that integrate expert knowledge and high-level summaries of surveillance data to allow decision-making about appropriate trade-offs between the cost of data and the precision of stockpile reliability estimates.