TY - CONF
TI - Why do simple algorithms for triangle enumeration work in the real world?
AU - Berry, J.W.
AU - Fostvedt, L.K.
AU - Nordman, D.J.
AU - Phillips, C.A.
AU - Seshadhri, C.
AU - Wilson, A.G.
AB - Triangle enumeration is a fundamental graph operation. Despite the lack of provably efficient (linear, or slightly super-linear) worst-case algorithms for this problem, practitioners run simple, efficient heuristics to find all triangles in graphs with millions of vertices. How are these heuristics exploiting the structure of these special graphs to provide major speedups in running time? We study one of the most prevalent algorithms used by practitioners. A trivial algorithm enumerates all paths of length 2, and checks if each such path is incident to a triangle. A good heuristic is to enumerate only those paths of length 2 where the middle vertex has the lowest degree. It is easily implemented and is empirically known to give remarkable speedups over the trivial algorithm. We study the behavior of this algorithm over graphs with heavy-tailed degree distributions, a defining feature of real-world graphs. The erased configuration model (ECM) efficiently generates a graph with asymptotically (almost) any desired degree sequence. We show that the expected running time of this algorithm over the distribution of graphs created by the ECM is controlled by the l4/3-norm of the degree sequence. As a corollary of our main theorem, we prove expected linear-time performance for degree sequences following a power law with exponent α ≥ 7/3, and non-trivial speedup whenever α ∈ (2,3).
C2 - 2014///
C3 - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
DA - 2014///
DO - 10.1145/2554797.2554819
SP - 225-234
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-84893281676&partnerID=MN8TOARS
ER -
TY - JOUR
TI - A Pilot Study Teaching Metrology in an Introductory Statistics Course
AU - Casleton, Emily
AU - Beyler, Amy
AU - Genschel, Ulrike
AU - Wilson, Alyson
T2 - Journal of Statistics Education
AB - Undergraduate students who have just completed an introductory statistics course often lack deep understanding of variability and enthusiasm for the field of statistics. This paper argues that by introducing the commonly underemphasized concept of measurement error, students will have a better chance of attaining both. We further present lecture materials and activities that introduce metrology, the science of measurement, which were developed and tested in a pilot study at Iowa State University. These materials explain how to characterize sources of variability in a dataset, in a way that is natural and accessible because the sources of variability are observable. Everyday examples of measurements, such as the amount of gasoline pumped into a car, are presented, and the consequences of variability within those measurements are discussed. To gauge the success of the material, students' initial and subsequent understanding of variability and their attitude toward the usefulness of statistics were analyzed in a comparative study. Questions from the CAOS and ARTIST assessments that pertain to using variability to make comparisons, understanding the standard deviation, and using graphical representations of variability were included in the assessment. The results of the comparative study indicate that most students who were exposed to the material improved their understanding of variability and had a greater appreciation of the value of statistics.
DA - 2014/11//
PY - 2014/11//
DO - 10.1080/10691898.2014.11889710
VL - 22
IS - 3
J2 - Journal of Statistics Education
LA - en
OP -
SN - 1069-1898
UR - http://dx.doi.org/10.1080/10691898.2014.11889710
DB - Crossref
KW - Variability
KW - Statistics curriculum
KW - Undergraduate statistics
KW - Deep understanding
KW - Data collection
ER -
TY - JOUR
TI - On Coverage-Based Attack Profiles
AU - Rivers, Anthony T.
AU - Vouk, Mladen A.
AU - Williams, Laurie
T2 - 2014 IEEE EIGHTH INTERNATIONAL CONFERENCE ON SOFTWARE SECURITY AND RELIABILITY - COMPANION (SERE-C 2014)
AB - Automated cyber attacks tend to be schedule and resource limited. The primary progress metric is often "coverage" of pre-determined "known" vulnerabilities that may not have been patched, along with possible zero-day exploits (if such exist). We present and discuss a hypergeometric process model that describes such attack patterns. We used web request signatures from the logs of a production web server to assess the applicability of the model.
DA - 2014///
PY - 2014///
DO - 10.1109/sere-c.2014.15
SP - 5-6
KW - security
KW - coverage
KW - models
KW - attack
KW - profile
ER -
TY - JOUR
TI - Discussion of 'Methods for planning repeated measures accelerated degradation tests'
AU - Reese, C. Shane
AU - Wilson, Alyson G.
T2 - APPLIED STOCHASTIC MODELS IN BUSINESS AND INDUSTRY
DA - 2014///
PY - 2014///
DO - 10.1002/asmb.2090
VL - 30
IS - 6
SP - 674-676
SN - 1526-4025
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-84919762822&partnerID=MN8TOARS
ER -
TY - JOUR
TI - Bayesian Binomial Assurance Tests for System Reliability Using Component Data
AU - Hamada, M. S.
AU - Wilson, A. G.
AU - Weaver, B. P.
AU - Griffiths, R. W.
AU - Martz, H. F.
T2 - JOURNAL OF QUALITY TECHNOLOGY
AB - This paper illustrates the development of Bayesian assurance test plans for system reliability assuming that binomial data will be collected on the system and that previous information is available from component testing. The posterior consumer's and producer's risks are used as the criteria for developing the test plan. Using the previous component information reduces the number of tests needed to achieve the same levels of risk. The proposed methodology is illustrated with two examples.
DA - 2014/1//
PY - 2014/1//
DO - 10.1080/00224065.2014.11917952
VL - 46
IS - 1
SP - 24-32
SN - 0022-4065
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-84894543868&partnerID=MN8TOARS
KW - Consumer's and Producer's Posterior Risk
KW - Demonstration Test
KW - Hierarchical Model
ER -