Search

Local Structure Graph Models (LSGMs) describe network data by modeling, and thereby controlling, the local structure of networks in a direct and interpretable manner. Specification of such models requires identifying three factors: a saturated, or maximally possible, graph; a neighborhood structure of dependent potential edges; and, lastly, a model form prescribed by full conditional binary distributions with appropriate “centering” steps and dependence parameters. This last aspect particularly distinguishes LSGMs from other model formulations for network data. In this article, we explore the expanded LSGM structure to incorporate dependencies among edges that form potential triangles, thus explicitly representing transitivity in the conditional probabilities that govern edge realization. Two networks previously examined in the literature, the Faux Mesa High friendship network and the 2000 college football network, are analyzed with such models, with a focus on assessing the manner in which terms reflecting two-way and three-way dependencies among potential edges influence the data structures generated by models that incorporate them. One conclusion reached is that explicit modeling of three-way dependencies is not always needed to reflect the observed level of transitivity in an actual graph. Another conclusion is that understanding the manner in which a model represents a given problem is enhanced by examining several aspects of model structure, not just the number of some particular topological structure generated by a fitted model.

Listing all triangles is a fundamental graph operation. Triangles can have important interpretations in real-world graphs, especially social and other interaction networks. 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 in which 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 ℓ4/3-norm of the degree sequence. Norms of the degree sequence are a measure of the heaviness of the tail, and it is precisely this feature that allows non trivial speedups of simple triangle enumeration algorithms. 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).

Abstract: A variety of existing symmetric parametric models for 3-D rotations found in both statistical and materials science literatures are considered from the point of view of the “uniform-axis-random-spin” (UARS) construction. One-sample Bayes methods for non-informative priors are provided for all of these models and attractive frequentist properties for corresponding Bayes inference on the model parameters are confirmed. Taken together with earlier work, the broad efficacy of non-informative Bayes inference for symmetric distributions on 3-D rotations is conclusively demonstrated. [Copyright &y& Elsevier]

Abstract: We consider likelihood and Bayes analyses for the symmetric matrix von Mises–Fisher (matrix Fisher) distribution, which is a common model for three-dimensional orientations (represented by orthogonal matrices with a positive determinant). One important characteristic of this model is a rotation matrix representing the modal rotation, and an important challenge is to establish accurate confidence regions for it with an interpretable geometry for practical implementation. While we provide some extensions of one-sample likelihood theory (e.g., Euler angle parametrizations of modal rotation), our main contribution is the development of MCMC-based Bayes inference through non-informative priors. In one-sample problems, the Bayes methods allow the construction of inference regions with transparent geometry and accurate frequentist coverages in a way that standard likelihood inference cannot. Simulation is used to evaluate the performance of Bayes and likelihood inference regions. Furthermore, we illustrate how the Bayes framework extends inference from one-sample problems to more complicated one-way random effects models based on the symmetric matrix Fisher model in a computationally straightforward manner. The inference methods are then applied to a human kinematics example for illustration. [Copyright &y& Elsevier]