Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for +publisher:"University of Colorado" +contributor:("Daniel Larremore"). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


University of Colorado

1. Broido, Anna. Characterizing the tails of degree distributions in real-world networks.

Degree: PhD, Applied Mathematics, 2019, University of Colorado

This is a thesis about how to characterize the statistical structure of the tails of degree distributions of real-world networks. The primary contribution is a statistical test of the prevalence of scale-free structure in real-world networks. A central claim in modern network science is that real-world networks are typically "scale free," meaning that the fraction of nodes with degree k follows a power law, decaying like k-a, often with 2 < a< 3. However, empirical evidence for this belief derives from a relatively small number of real-world networks. In the first section, we test the universality of scale-free structure by applying state-of-the-art statistical tools to a large corpus of nearly 1000 network data sets drawn from social, biological, technological, and informational sources. We fit the power-law model to each degree distribution, test its statistical plausibility, and compare it via a likelihood ratio test to alternative, non-scale-free models, e.g., the log-normal. Across domains, we find that scale-free networks are rare, with only 4% exhibiting the strongest-possible evidence of scale-free structure and 52% exhibiting the weakest-possible evidence. Furthermore, evidence of scale-free structure is not uniformly distributed across sources: social networks are at best weakly scale free, while a handful of technological and biological networks can be called strongly scale free. These results undermine the universality of scale-free networks and reveal that real-world networks exhibit a rich structural diversity that will likely require new ideas and mechanisms to explain. A core methodological component of addressing the ubiquity of scale-free structure in real-world networks is an ability to fit a power law to the degree distribution. In the second section, we numerically evaluate and compare, using both synthetic data with known structure and real-world data with unknown structure, two statistically principled methods for estimating the tail parameters for power-law distributions, showing that in practice, a method based on extreme value theory and a sophisticated bootstrap and the more commonly used method based an empirical minimization approach exhibit similar accuracy. Advisors/Committee Members: Aaron Clauset, Jem Corcoran, Daniel Larremore, Manuel Lladser, Juan Restrepo.

Subjects/Keywords: networks; power law; scale free; Applied Statistics; Other Applied Mathematics; Probability; Statistical Methodology; Statistical Models

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Broido, A. (2019). Characterizing the tails of degree distributions in real-world networks. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/143

Chicago Manual of Style (16th Edition):

Broido, Anna. “Characterizing the tails of degree distributions in real-world networks.” 2019. Doctoral Dissertation, University of Colorado. Accessed January 26, 2021. https://scholar.colorado.edu/appm_gradetds/143.

MLA Handbook (7th Edition):

Broido, Anna. “Characterizing the tails of degree distributions in real-world networks.” 2019. Web. 26 Jan 2021.

Vancouver:

Broido A. Characterizing the tails of degree distributions in real-world networks. [Internet] [Doctoral dissertation]. University of Colorado; 2019. [cited 2021 Jan 26]. Available from: https://scholar.colorado.edu/appm_gradetds/143.

Council of Science Editors:

Broido A. Characterizing the tails of degree distributions in real-world networks. [Doctoral Dissertation]. University of Colorado; 2019. Available from: https://scholar.colorado.edu/appm_gradetds/143


University of Colorado

2. Broido, Anna D. Characterizing the Tails of Degree Distributions in Real-World Networks.

Degree: PhD, 2019, University of Colorado

This is a thesis about how to characterize the statistical structure of the tails of degree distributions of real-world networks. The primary contribution is a statistical test of the prevalence of scale-free structure in real-world networks. A central claim in modern network science is that real-world networks are typically "scale free," meaning that the fraction of nodes with degree k follows a power law, decaying like k^-a, often with 2 < a < 3. However, empirical evidence for this belief derives from a relatively small number of real-world networks. In the first section, we test the universality of scale-free structure by applying state-of-the-art statistical tools to a large corpus of nearly 1000 network data sets drawn from social, biological, technological, and informational sources. We fit the power-law model to each degree distribution, test its statistical plausibility, and compare it via a likelihood ratio test to alternative, non-scale-free models, e.g., the log-normal. Across domains, we find that scale-free networks are rare, with only 4% exhibiting the strongest-possible evidence of scale-free structure and 52% exhibiting the weakest-possible evidence. Furthermore, evidence of scale-free structure is not uniformly distributed across sources: social networks are at best weakly scale free, while a handful of technological and biological networks can be called strongly scale free. These results undermine the universality of scale-free networks and reveal that real-world networks exhibit a rich structural diversity that will likely require new ideas and mechanisms to explain. A core methodological component of addressing the ubiquity of scale-free structure in real-world networks is an ability to fit a power law to the degree distribution. In the second section, we numerically evaluate and compare, using both synthetic data with known structure and real-world data with unknown structure, two statistically principled methods for estimating the tail parameters for power-law distributions, showing that in practice, a method based on extreme value theory and a sophisticated bootstrap and the more commonly used method based an empirical minimization approach exhibit similar accuracy. Advisors/Committee Members: Aaron Clauset, Jem Corcoran, Daniel Larremore, Manuel Lladser, Juan Restrepo.

Subjects/Keywords: networks; power law; scale free; Applied Mathematics

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Broido, A. D. (2019). Characterizing the Tails of Degree Distributions in Real-World Networks. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/153

Chicago Manual of Style (16th Edition):

Broido, Anna D. “Characterizing the Tails of Degree Distributions in Real-World Networks.” 2019. Doctoral Dissertation, University of Colorado. Accessed January 26, 2021. https://scholar.colorado.edu/appm_gradetds/153.

MLA Handbook (7th Edition):

Broido, Anna D. “Characterizing the Tails of Degree Distributions in Real-World Networks.” 2019. Web. 26 Jan 2021.

Vancouver:

Broido AD. Characterizing the Tails of Degree Distributions in Real-World Networks. [Internet] [Doctoral dissertation]. University of Colorado; 2019. [cited 2021 Jan 26]. Available from: https://scholar.colorado.edu/appm_gradetds/153.

Council of Science Editors:

Broido AD. Characterizing the Tails of Degree Distributions in Real-World Networks. [Doctoral Dissertation]. University of Colorado; 2019. Available from: https://scholar.colorado.edu/appm_gradetds/153


University of Colorado

3. Ghasemian, Amir. Limits of Model Selection, Link Prediction, and Community Detection.

Degree: PhD, 2019, University of Colorado

Relational data has become increasingly ubiquitous nowadays. Networks are very rich tools in graph theory, which represent real world interactions through a simple abstract graph, including nodes and edges. Network analysis and modeling has gained extremely wide attentions from the researchers in various disciplines, such as computer science, social science, biology, economics, electrical engineering, and physics. Network analysis is the study of the network topology to answer a variety of application-based questions regarding the original real world problem. For example in social network analysis the questions are related to how people interact with each other in online social networks, or in collaboration networks, how diseases propagate or how information flows through a network, or how to control a disease or food outbreak. In electric networks like power grids or in internet networks, the questions can be related to vulnerability assessment of the networks to be prepared for power outage or internet blackout. In biological network analysis, the questions are related to how different diseases are related to each other, which can be useful in discovering new symptoms of diseases and producing and developing new medicines. It appears clearly that the reason of the importance of this interdisciplinary area of science, is due to its widespread applications which involves scientists and researchers with a variety of background and interests. Although networks are much simpler compared to the original complex systems, the interactions among the nodes in the real-world network may seem random, and capturing patterns on these entities is not trivial. There are tremendous questions about inference on networks, which makes this topic very attractive for researchers in the field. In this dissertation we answer some of the questions regarding this topic in two lines of study: one focused on experimental analyses and one focused on theoretical limitations. In Chapter 2 we look at community detection, a common graph mining task in network inference, which seeks an unsupervised decomposition of a network into groups based on statistical regularities in network connectivity. Although many such algorithms exist, community detection’s No Free Lunch theorem implies that no algorithm can be optimal across all inputs. However, little is known in practice about how different algorithms over or underfit to real networks, or how to reliably assess such behavior across algorithms. We present a broad investigation of over and underfitting across 16 state-of-the-art community detection algorithms applied to a novel benchmark corpus of 572 structurally diverse real-world networks. We find that (i) algorithms vary widely in the number and composition of communities they find, given the same input; (ii) algorithms can be clustered into distinct high-level groups based on similarities of their outputs on real-world networks; (iii) algorithmic differences induce wide variation in accuracy on link-based learning tasks; and,… Advisors/Committee Members: Aaron Clauset, Cristopher Moore, Aram Galstyan, Paul Constantine, Daniel Larremore.

Subjects/Keywords: community detection; link description; link prediction; model selection; overfitting; underfitting; Artificial Intelligence and Robotics; Computer Sciences

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Ghasemian, A. (2019). Limits of Model Selection, Link Prediction, and Community Detection. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/csci_gradetds/206

Chicago Manual of Style (16th Edition):

Ghasemian, Amir. “Limits of Model Selection, Link Prediction, and Community Detection.” 2019. Doctoral Dissertation, University of Colorado. Accessed January 26, 2021. https://scholar.colorado.edu/csci_gradetds/206.

MLA Handbook (7th Edition):

Ghasemian, Amir. “Limits of Model Selection, Link Prediction, and Community Detection.” 2019. Web. 26 Jan 2021.

Vancouver:

Ghasemian A. Limits of Model Selection, Link Prediction, and Community Detection. [Internet] [Doctoral dissertation]. University of Colorado; 2019. [cited 2021 Jan 26]. Available from: https://scholar.colorado.edu/csci_gradetds/206.

Council of Science Editors:

Ghasemian A. Limits of Model Selection, Link Prediction, and Community Detection. [Doctoral Dissertation]. University of Colorado; 2019. Available from: https://scholar.colorado.edu/csci_gradetds/206

.