🔖 On random graphs by Paul Erdős and Alfréd Rényi (1959)

Bookmarked On Random Graphs. I by Paul Erdős and Alfréd Rényi (Publicationes Mathematicae. 6: 290–297.)

Original source of Erdős–Rényi model.

In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs. They are named after mathematicians Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959,[1][2] while Edgar Gilbert introduced the other model contemporaneously and independently of Erdős and Rényi.[3] In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely; in the model introduced by Gilbert, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

hat tip: Linked: The New Science Of Networks by Albert-László Barabási

🔖 Collective Dynamics of Small-World Networks by Duncan J. Watts & Steven H. Strogatz

Bookmarked Collective dynamics of ‘small-world’ networks by Duncan J. Watts & Steven H. Strogatz (Nature | VOL 393)
Networks of coupled dynamical systems have been used to model biological oscillators1–4, Josephson junction arrays5,6, excitable media7, neural networks8–10, spatial games11, genetic control networks12 and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by analogy with the small-world phenomenon13,14 (popularly known as six degrees of separation15). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.
hat tip: Linked: The New Science Of Networks by Albert-László Barabási

👓 Decades-Old Graph Problem Yields to Amateur Mathematician | Quanta Magazine

Read Decades-Old Graph Problem Yields to Amateur Mathematician (Quanta Magazine)
By making the first progress on the “chromatic number of the plane” problem in over 60 years, an anti-aging pundit has achieved mathematical immortality.

🔖 Emerging Frontiers of Neuroengineering: A Network Science of Brain Connectivity

Bookmarked Emerging Frontiers of Neuroengineering: A Network Science of Brain Connectivity (arxiv.org)
Neuroengineering is faced with unique challenges in repairing or replacing complex neural systems that are composed of many interacting parts. These interactions form intricate patterns over large spatiotemporal scales, and produce emergent behaviors that are difficult to predict from individual elements. Network science provides a particularly appropriate framework in which to study and intervene in such systems, by treating neural elements (cells, volumes) as nodes in a graph and neural interactions (synapses, white matter tracts) as edges in that graph. Here, we review the emerging discipline of network neuroscience, which uses and develops tools from graph theory to better understand and manipulate neural systems, from micro- to macroscales. We present examples of how human brain imaging data is being modeled with network analysis and underscore potential pitfalls. We then highlight current computational and theoretical frontiers, and emphasize their utility in informing diagnosis and monitoring, brain-machine interfaces, and brain stimulation. A flexible and rapidly evolving enterprise, network neuroscience provides a set of powerful approaches and fundamental insights critical to the neuroengineer's toolkit.
17 pages, 6 figures. Manuscript accepted to the journal Annual Review of Biomedical Engineering [1]

References

[1]
D. Bassett S., A. Khambhati N., and S. Grafton T., “Emerging Frontiers of Neuroengineering: A Network Science of Brain Connectivity,” arXiv, 23-Dec-2016. [Online]. Available: https://arxiv.org/abs/1612.08059. [Accessed: 03-Jan-2017]

Network Science by Albert-László Barabási

Bookmarked Network Science by Albert-László BarabásiAlbert-László Barabási (Cambridge University Press)
I ran across a link to this textbook by way of a standing Google alert, and was excited to check it out. I was immediately disappointed to think that I would have to wait another month and change for the physical textbook to be released, but made my pre-order directly. Then with a bit of digging around, I realized that individual chapters are available immediately to quench my thirst until the physical text is printed next month.

The power of network science, the beauty of network visualization.

Network Science, a textbook for network science, is freely available under the Creative Commons licence. Follow its development on Facebook, Twitter or by signing up to our mailing list, so that we can notify you of new chapters and developments.

The book is the result of a collaboration between a number of individuals, shaping everything, from content (Albert-László Barabási), to visualizations and interactive tools (Gabriele Musella, Mauro Martino, Nicole Samay, Kim Albrecht), simulations and data analysis (Márton Pósfai). The printed version of the book will be published by Cambridge University Press in 2016. In the coming months the website will be expanded with an interactive version of the text, datasets, and slides to teach the material.

Book Contents

Personal Introduction
1. Introduction
2. Graph Theory
3. Random Networks
4. The Scale-Free Property
5. The Barabási-Albert Model
6. Evolving Networks
7. Degree Correlations
8. Network Robustness
9. Communities
10. Spreading Phenomena
Usage & Acknowledgements
About

Albert-László Barabási
on Network Science (book website)

Networks are everywhere, from the Internet, to social networks, and the genetic networks that determine our biological existence. Illustrated throughout in full colour, this pioneering textbook, spanning a wide range of topics from physics to computer science, engineering, economics and the social sciences, introduces network science to an interdisciplinary audience. From the origins of the six degrees of separation to explaining why networks are robust to random failures, the author explores how viruses like Ebola and H1N1 spread, and why it is that our friends have more friends than we do. Using numerous real-world examples, this innovatively designed text includes clear delineation between undergraduate and graduate level material. The mathematical formulas and derivations are included within Advanced Topics sections, enabling use at a range of levels. Extensive online resources, including films and software for network analysis, make this a multifaceted companion for anyone with an interest in network science.

Source: Cambridge University Press

The textbook is available for purchase in September 2016 from Cambridge University Press. Pre-order now on Amazon.com.

If you’re not already doing so, you should follow Barabási on Twitter.