Multidisciplinary University Research Initiative (MURI) Project,
funded by the Office of Naval Research (ONR)

• Home
• News
• Publications
• People
  • Padhraic Smyth
  • Carter Butts
  • David Eppstein
  • Carter Butts
  • David Eppstein
  • Michael Goodrich
  • David Hunter
  • Mark S. Handcock
  • David Mount
  • Graduate Students
• Previous Meetings
  • June 2011
  • November 2010
  • May 2010
  • December 2009
  • August 2009
  • April 2009
  • November 2008
• Software and Data
• Literature Links

Recent Publications

Fundamentals of Exponential Random Graph Models and Network Analysis

• Computational statistical methods for social network models. Hunter, David R., Krivitsky, Pavel N. and Michael Schweinberger (order of authors is alphabetical: all three authors made equal contributions) (2012). Journal of Computational and Graphical Statistics, 21, 856-882.
• Bernoulli Graph Bounds for General Random Graphs. C. Butts, Sociological Methodology, 2011.
• Adjusting for network size and composition effects in exponential-family random graph models. M. Handock and P. Krivitsky and Martina Morris. 2009, http://arxiv.org/abs/1004.5328v1.
• Revisiting the Foundations of Network Analysis. C.T. Butts, Science, 325, 414-416.
• A Note on Generalized Edges (MBS 10-03) C.T. Butts, IMBS Technical Report.
• Instability, Sensitivity, and Degeneracy of Discrete Exponential Families. M. Schweinberger, Journal of the American Statistical Association, Vol. 106, No. 496, 1361-1370.
• Comparison of Maximum Pseudo Likelihood and Maximum Likelihood Estimation of Exponential Random Graph Models. Mark Handcock with Marijtje van Duijn and Krista Gile. Social Networks, 30, 1, 52-62.

Scalable Algorithms for Statistical Network Modeling

• Model-based clustering of large networks. Vu, Duy Q., Hunter, David R., and Michael Schweinberger (2012). Annals of Applied Statistics, in press.
• Schweinberger, Michael and Mark S. Handcock. Hierarchical exponential-family random graph models with local dependence. Under review.
• Vu DQ, Asuncion AU, Hunter DR, Smyth P (2011), Continuous-Time Regression Models for Longitudinal Networks, Advances in Neural Information Processing Systems 24 (NIPS 2011), to appear.
• Modeling relational events via latent classes. C. DuBois & P. Smyth. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 2010.
• Particle filtered MCMC-MLE with connections to contrastive divergence. A. Asuncion, Q. Liu, A. T. Ihler, and P. Smyth. Proceedings of the 27th International Conference on Machine Learning (ICML), July 2010.
• The h-index of a graph and its application to dynamic subgraph statistics. D. Eppstein & E. S. Spiro. Proceedings of Algorithms and Data Structures Symposium (WADS), Banff, Canada, August 2009; Springer-Verlag, Lecture Notes in Computer Science 5664, pp. 2789
• A steplength algorithm for fitting ERGMs. R.M. Hummel, M.S. Handcock, D.R. Hunter, accepted at Journal of Computational and Graphical Statistics.
• Learning with Blocks: Composite Likelihood and Contrastive Divergence, A. Asuncion, Q. Liu, A. T. Ihler, and P. Smyth. Thirtheenth International Conference on AI and Statistics, May 2010.
• Bayesian Meta-Analysis of Social Network Data via Conditional Uniform Graph Quantiles (MBS 10-04) C.T. Butts, Sociological Methodology, forthcoming.
• Particle-filtered MCMC-MLE with connections to contrastive divergence, A. Asuncion, Q. Liu, A. Ihler, and P. Smyth, Proceedings of the International Conference on Machine Learning (ICML), 2010.
• Logistic Network Regression for Scalable Analysis of Networks with Joint Edge/Vertex Dynamics. Almquist, Zack W. and Butts, Carter T. IMBS Technical Report MBS 11-03, University of California, Irvine.

Geometric and Spatial Embedding Methods

• S. Arya, G. D. da Fonseca, and D. M. Mount. Polytope approximation and the Mahler volume. Proc. 23rd Annu. ACM-SIAM Sympos. Discrete Algorithms, 2012 (to appear.)
• M.T. Goodrich and J.A. Simons, Fully Retroactive Approximate Range and Nearest Neighbor Searching," 22nd International Symposium on Algorithms and Computation (ISAAC), 2011.
• M.T. Goodrich and D. Strash, Priority Range Trees," Proc. 21st International Symposium on Algorithms and Computation (ISAAC), LNCS, vol. 6506, 2010, 97-108.
• Adjacency-preserving spatial treemaps. K. Buchin, D. Eppstein, M. Löffler, M. Nöllenburg, and R. I. Silveira. 12th International Symposium on Algorithms and Data Structures (WADS 2011), New York, 2011. Lecture Notes in Comp. Sci. 6844, 2011, pp. 159-170.
• Approximate Polytope Membership Queries. S. Arya, G. D. da Fonseca and D. M. Mount. Proc. 43rd ACM Symp. on Theory of Computing (STOC 2011), 2011, 579-586.
• Representing Degree Distributions, Clustering, and Homophily in Social Networks With Latent Cluster Random Effects Models. Mark Handcock with Pavel Krivitsky, Peter Hoff and Adrian E. Raftery. Social Networks, 31,3, 204-213, 2009.
• Tight Lower Bounds for Halfspace Range Searching, S. Arya and D. M. Mount and J. Xia, Proc. 26th Annual Symp. on Computational Geometry (SoCG 2010), 2010. (Accepted for publication in Discrete and Computational Geometry.)
• A Dynamic Data Structure for Approximate Range Searching, D. M. Mount and E. Park, Proc. 26th Annual Symp. on Computational Geometry (SoCG 2010), 2010.
• A Unified Approach to Approximate Proximity Searching, S. Arya, G. D. da Fonseca, and D. M. Mount, Proc. 18th European Symposium on Algorithms (ESA 2010), 2010.
• Spatio-temporal Range Searching Over Compressed Kinetic Sensor Data, S. A. Friedler and D. M. Mount, Proc. 18th European Symposium on Algorithms (ESA 2010), 2010.
• Maintaining Nets and Net Trees under Incremental Motion, M. Cho, D. M. Mount, and E. Park, in Proc. 20th Intl. Symp. on Algorithms and Computation (ISAAC 2009),Lecture Notes Comput. Sci., Vol. LNCS 5878, Springer-Verlag, 1134-1143, (doi: 10.1007/978-3-642-10631-6_114).
• Particle-based variational inference for continuous systems. A. T. Ihler, A. J. Frank, P. Smyth, Proceedings of the 22nd Neural Information Processing Conference (NIPS), Dec 2009.
• Succinct Greedy Geometric Routing in the Euclidean Plane, M. T. Goodrich and D. Strash, in Proc. 20th Intl. Symp. on Algorithms and Computation (ISAAC 2009), 2009.
• The Effect of Corners on the Complexity of Approximate Range Searching, S. Arya, T. Malamatos, and D. M. Mount, Discrete and Computational Geometry, 41 (2009), 398-443.
• Compressing Kinetic Data From Sensor Networks, S. Friedler and D. M. Mount, Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 2009), Springer Lecture Notes LNCS 5804, 2009, 191-202.
• Space-Time Tradeoffs for Approximate Nearest Neighbor Searching, S. Arya, T. Malamatos, and D. M. Mount, Journal of the ACM, 57 (2009), 1-54.
• Approximate Range Searching: The Absolute Model, G. D. da Fonseca and D. M. Mount, Computational Geometry, 43 (2010), 434-444, (doi: 10.1016/j.comgeo.2008.09.009).
• Approximation Algorithm for the Kinetic Robust K-Center Problem, S. Friedler and D. M. Mount, Computational Geometry, Volume 43 Issue 6-7, August, 2010.

Relational Event Models, Dynamic Models, and Behavioral Network Models

• Stochastic blockmodeling of relational event dynamics. Christopher DuBois, Carter Butts, Padhraic Smyth. AI STATS 2013.
• Hierarchical models for relational event sequences. Christopher DuBois, Carter T Butts, Daniel McFarland, Padhraic Smyth. To appear in Journal of Mathematical Psychology.
• Dynamic egocentric models for citation networks. D. Q. Vu, A. Asuncion, D. R. Hunter, P. Smyth Proceedings of the 18th International Conference on Machine Learning (ICML 2011), 2011, to appear.
• Latent set models for two-mode network data. C. DuBois, J. Foulds, P. Smyth Proceedings of the 5th International AAAI Conference on Weblogs and Social Media, 2011, to appear.
• A dynamic relational infinite feature model for longitudinal social networks. J. Foulds, A. Asuncion, C. DuBois, C. T. Butts, P. Smyth Proceedings of the 14th International Conference on AI and Statistics, April 2011.
• A Separable Model for Dynamic Networks. Mark Handcock with Pavel N. Krivitsky. Under review, 2010. http://arxiv.org/abs/1011.1937v1.
• A Description of Within-family Resource Exchange Networks in a Malawian Village. Mark Handcock with Gail E. Potter. Demographic Research, 23, 6, pp. 117–152. doi:10.4054/DemRes.2010.23.6. 2010.
• Change and External Events in Computer-Mediated Citation Networks: English Language Weblogs and the 2004 US Electoral Cycle. C.T.Butts and B.R. Cross, Journal of Social Structure, 10.

Statistical Modeling of Text and Networks

• Distributed algorithms for topic models, D. Newman, A. Asuncion, P. Smyth, M. Welling, Journal of Machine Learning Research, 2009.
• Asynchronous distributed estimation of topic models for document analysis, A. Asuncion, P. Smyth, M. Welling, Statistical Methodology, 2010.

Measurement of Large-scale Network Structure

• A Walk in Facebook: Uniform Sampling of Users in Online Social Networks. M. Gjoka, M. Kurant, C.T. Butts, A. Markopoulou. Electronic preprint arXiv:0906.0060. Proceedings of IEEE INFOCOM 2010.

Network Visualization:

• Drawing graphs in the plane with a prescribed outer face and polynomial area. E. Chambers, D. Eppstein, M. T. Goodrich, and M. Löffler. Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010. Lecture Notes in Comp. Sci. 6502, 2011, pp. 129-140, Springer-Verlag.
• Lombardi drawings of graphs. C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Nöllenburg. Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010. Lecture Notes in Comp. Sci. 6502, 2011, pp. 195-207, Springer-Verlag. Invited talk at 7th Dutch Computational Geometry Day, Eindhoven, the Netherlands, 2010. J. Graph Algorithms and Applications 16(1):85-108, 2012 (special issue for GD 2010).
• Drawing trees with perfect angular resolution and polynomial area. C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Nöllenburg. Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010. Lecture Notes in Comp. Sci. 6502, 2011, pp. 183-194, Springer-Verlag.
• Optimal 3D angular resolution for low-degree graphs. D. Eppstein, M. Löffler, E. Mumford, and M. Nöllenburg. Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
• Confluent Hasse diagrams. D. Eppstein and J. Simons. Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
• Hardness of approximate compaction for nonplanar orthogonal graph drawings. M. J. Bannister and D. Eppstein. Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
• Planar and poly-arc Lombardi drawings. C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Löffler. Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
• Force-Directed Lombardi-Style Graph Drawing. Roman Chernobelskiy, Kathryn Cunningham, Michael Goodrich, Stephen Kobourov and Lowell Trott. Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
• Planar Drawings of Higher-Genus Graphs,C.A. Duncan, M.T. Goodrich, S.G. Kobourov. Proc. 17th Int. Symp. on Graph Drawing (GD), Lecture Notes in Computer Science, Springer, 2009.

Network Algorithms

• M.T. Goodrich and P. Pszona, External-Memory Network Analysis Algorithms for Naturally Sparse Graphs," European Symposium on Algorithms (ESA), 2011.
• A.U. Asuncion and M.T. Goodrich, Turning Privacy Leaks into Floods: Surreptitious Discovery of Social Network Friendships and Other Sensitive Binary Attribute Vectors," Proc. Workshop on Privacy in the Electronic Society (WPES), held in conjunction with the 17th ACM Conference on Computer and Communications Security (CCS), 2010, 21-30.
• L. Arge, M.T. Goodrich, and N. Sitchinava, Parallel External Memory Graph Algorithms," 24th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2010, 1-11.
• Randomized speedup of the Bellman-Ford algorithm. M. J. Bannister and D. Eppstein. Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan, 2012.
• Category-based routing in social networks: membership dimension and the small-world phenomenon. D. Eppstein, M. T. Goodrich, M. Löffler D. Strash, and L. Trott. Workshop on Graph Algorithms and Applications, Zürich, Switzerland, July 2011. International Conference on Computational Aspects of Social Networks (CASoN 2011), Salamanca, Spain, October 2011.
• Listing all maximal cliques in large sparse real-world graphs. D. Eppstein and D. Strash. 10th Int. Symp. Experimental Algorithms, Crete, 2011.
• Extended h-index parameterized data structures for computing dynamic subgraph statistics. D. Eppstein, M. T. Goodrich, D. Strash and L. Trott, Proc. 4th Int. Conf. on Combinatorial Optimization and Applications (COCOA 2010), Lecture Notes in Comp. Sci. 6508, Springer-Verlag, 2010, pp. 128–141.
• D. Eppstein and M.T. Goodrich. Studying (non-planar) road networks through an algorithmic lens, Proc. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), 2008, 125–134. (Best Paper award).
• D. Eppstein, M.T. Goodrich, and D. Strash, Linear-time algorithms for geometric graphs with sublinearly many crossings, 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, 150–159.
• Reliable Resource Searching in P2P Networks, M.T. Goodrich, R. Tamassia, and N. Triandopoulos, J.Z. Sun. 5th International ICST Conference on Security and Privacy in Communication Networks (SecureComm), Lecture Notes of ICST, Springer, 2009.
• Going Off-road: Transversal Complexity in Road Networks,D. Eppstein, M.T. Goodrich, L. Trott. Proc. 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), 2009.

Hidden/network population sampling

• Respondent-Driven Sampling: An Assessment of Current Methodology. Mark Handcock with Krista J. Gile. Sociological Methodology, 40. doi: 10.1111/j.1467-9531.2010.01223.x. Published online June 28, 2010. Manuscript at http://arxiv.org/abs/0904.1855.
• Modeling Networks from Sampled Data. Mark Handcock and Krista Gile. Annals of Applied Statistics, 4, Number 1, 5-25.

Applications

• Schweinberger, Michael, Petrescu-Prahova, Miruna, and Duy Q. Vu. Disaster Response on September 11, 2001 Through the Lens of Statistical Network Analysis. Under review.

Archival Data and Software for Network Analysis

• US Census Spatial and Demographic Data in R: The UScensus2000 Suite of Packages. Zack W. Almquiest. Journal of Statistical Software. Vol. 37, Issue 6, Nov 2010.