✅ Data mining when each data point is a network
Karthikeyan Rajendran, Assimakis A. Kattis, Alexander Holiday, Risi Kondor, Ioannis G. Kevrekidis
https://arxiv.org/pdf/1612.02908v1
🔻 ABSTRACT
We discuss the problem of extending data mining approaches to cases in which data points arise in the form of individual graphs. Being able to find the intrinsic low-dimensionality in ensembles of graphs can be useful in a variety of modeling contexts, especially when coarse-graining the detailed graph information is of interest. One of the main challenges in mining graph data is the definition of a suitable pairwise similarity metric in the space of graphs. We explore two practical solutions to solving this problem: one based on finding subgraph densities, and one using spectral information. The approach is illustrated on three test data sets (ensembles of graphs); two of these are obtained from standard graph generating algorithms, while the graphs in the third example are sampled as dynamic snapshots from an evolving network simulation. We further incorporate these approaches with equation free techniques, demonstrating how such data mining approaches can enhance scientific computation of network evolution dynamics.
Karthikeyan Rajendran, Assimakis A. Kattis, Alexander Holiday, Risi Kondor, Ioannis G. Kevrekidis
https://arxiv.org/pdf/1612.02908v1
🔻 ABSTRACT
We discuss the problem of extending data mining approaches to cases in which data points arise in the form of individual graphs. Being able to find the intrinsic low-dimensionality in ensembles of graphs can be useful in a variety of modeling contexts, especially when coarse-graining the detailed graph information is of interest. One of the main challenges in mining graph data is the definition of a suitable pairwise similarity metric in the space of graphs. We explore two practical solutions to solving this problem: one based on finding subgraph densities, and one using spectral information. The approach is illustrated on three test data sets (ensembles of graphs); two of these are obtained from standard graph generating algorithms, while the graphs in the third example are sampled as dynamic snapshots from an evolving network simulation. We further incorporate these approaches with equation free techniques, demonstrating how such data mining approaches can enhance scientific computation of network evolution dynamics.
📄 Random walks and diffusion on networks
Naoki Masuda, Mason A. Porter, Renaud Lambiotte
https://arxiv.org/pdf/1612.03281v1
📌 ABSTRACT
Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models.
Naoki Masuda, Mason A. Porter, Renaud Lambiotte
https://arxiv.org/pdf/1612.03281v1
📌 ABSTRACT
Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models.
📄 Nonlocality in complex networks
Chengwei Wang, Celso Grebogi, Murilo S. Baptista
https://arxiv.org/pdf/1612.03193v1
📌 ABSTRACT
Understanding the interactions among nodes in complex networks are of great importance, since it shows how these nodes are cooperatively supporting the functioning of the systems. Scientists have developed numerous methods and approaches to uncover the underlying physical connectivity based on measurements of functional quantities of the nodes states. However, little is known about how this local connectivity impacts on the non-local interactions and exchanges of physical flows between arbitrary nodes. In this paper, we show how to determine the non-local interchange of physical flows between any pair of nodes in a complex network, even if they are not physically connected by an edge. We show that such non-local interactions can happen in a steady or dynamic state of either a linear or non-linear network. Our approach can be used to conservative flow networks and, under certain conditions, to bidirectional flow networks .
Chengwei Wang, Celso Grebogi, Murilo S. Baptista
https://arxiv.org/pdf/1612.03193v1
📌 ABSTRACT
Understanding the interactions among nodes in complex networks are of great importance, since it shows how these nodes are cooperatively supporting the functioning of the systems. Scientists have developed numerous methods and approaches to uncover the underlying physical connectivity based on measurements of functional quantities of the nodes states. However, little is known about how this local connectivity impacts on the non-local interactions and exchanges of physical flows between arbitrary nodes. In this paper, we show how to determine the non-local interchange of physical flows between any pair of nodes in a complex network, even if they are not physically connected by an edge. We show that such non-local interactions can happen in a steady or dynamic state of either a linear or non-linear network. Our approach can be used to conservative flow networks and, under certain conditions, to bidirectional flow networks .
📄 Unification of theoretical approaches for epidemic spreading on complex networks
Wei Wang, Ming Tang, H. Eugene #Stanley, Lidia A. Braunstein
https://arxiv.org/pdf/1612.04216v1
📌 ABSTRACT
Models of epidemic spreading on complex networks have attracted great attention among researchers in physics, mathematics, and epidemiology due to their success in predicting and controlling scenarios of epidemic spreading in real-world scenarios. To understand the interplay between epidemic spreading and the topology of a contact network, several outstanding theoretical approaches have been developed. An accurate theoretical approach describing the spreading dynamics must take both the network topology and dynamical correlations into consideration at the expense of increasing the complexity of the equations. In this short survey we unify the most widely used theoretical approaches for epidemic spreading on complex networks in terms of increasing complexity, including the mean-field, the heterogeneous mean-field, the quench mean-field, dynamical message-passing, link percolation, and pairwise approximation. We build connections among these approaches to provide new insights into developing an accurate theoretical approach to spreading dynamics on complex networks.
Wei Wang, Ming Tang, H. Eugene #Stanley, Lidia A. Braunstein
https://arxiv.org/pdf/1612.04216v1
📌 ABSTRACT
Models of epidemic spreading on complex networks have attracted great attention among researchers in physics, mathematics, and epidemiology due to their success in predicting and controlling scenarios of epidemic spreading in real-world scenarios. To understand the interplay between epidemic spreading and the topology of a contact network, several outstanding theoretical approaches have been developed. An accurate theoretical approach describing the spreading dynamics must take both the network topology and dynamical correlations into consideration at the expense of increasing the complexity of the equations. In this short survey we unify the most widely used theoretical approaches for epidemic spreading on complex networks in terms of increasing complexity, including the mean-field, the heterogeneous mean-field, the quench mean-field, dynamical message-passing, link percolation, and pairwise approximation. We build connections among these approaches to provide new insights into developing an accurate theoretical approach to spreading dynamics on complex networks.
🔑 GENERAL FEATURES OF COMPLEX SYSTEMS
Y. Bar-Yam
New England Complex Systems Institute, Cambridge, MA, USA
🗒 Contents
1. Overview
2. Self-Organizing Patterns
3. Complexity, Scale and the Space of Possibilities
4. Evolution (Simple to Complex Patterns)
🎯 Keywords:
adaptive, altruism, clique, coherent, competition, complexity, cooperation, creativity, description, development, emergence, environment, evolution, fad, feedback, hierarchy, human civilization, information, interdependence, memory, network, observer, panic, pattern, possibilities, random, reductionism, relationship, scale, selfishness, self- organization, state, system 👇
Y. Bar-Yam
New England Complex Systems Institute, Cambridge, MA, USA
🗒 Contents
1. Overview
2. Self-Organizing Patterns
3. Complexity, Scale and the Space of Possibilities
4. Evolution (Simple to Complex Patterns)
🎯 Keywords:
adaptive, altruism, clique, coherent, competition, complexity, cooperation, creativity, description, development, emergence, environment, evolution, fad, feedback, hierarchy, human civilization, information, interdependence, memory, network, observer, panic, pattern, possibilities, random, reductionism, relationship, scale, selfishness, self- organization, state, system 👇
📋 Greedy Routing and the Algorithmic Small-World Phenomenom
Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Molla
🔗 https://arxiv.org/pdf/1612.05539v1
📌ABSTRACT
The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However, from today's perspective his model has several severe shortcomings that limit the applicability to real-world networks. In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study greedy routing in a more realistic random graph model (geometric inhomogeneous random graphs), which overcomes the previous shortcomings. Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks.
In this model, we show that greedy routing succeeds with constant probability, and in case of success almost surely finds a path that is an almost shortest path. Our results are robust to changes in the model parameters and the routing objective. Moreover, since constant success probability is too low for technical applications, we study natural local patching methods augmenting greedy routing by backtracking and we show that such methods can ensure success probability 1 in a number of steps that is close to the shortest path length.
These results also address the question of Krioukov et al. whether there are efficient local routing protocols for the internet graph. There were promising experimental studies, but the question remained unsolved theoretically. Our results give for the first time a rigorous and analytical answer, assuming our random graph model.
Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Molla
🔗 https://arxiv.org/pdf/1612.05539v1
📌ABSTRACT
The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However, from today's perspective his model has several severe shortcomings that limit the applicability to real-world networks. In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study greedy routing in a more realistic random graph model (geometric inhomogeneous random graphs), which overcomes the previous shortcomings. Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks.
In this model, we show that greedy routing succeeds with constant probability, and in case of success almost surely finds a path that is an almost shortest path. Our results are robust to changes in the model parameters and the routing objective. Moreover, since constant success probability is too low for technical applications, we study natural local patching methods augmenting greedy routing by backtracking and we show that such methods can ensure success probability 1 in a number of steps that is close to the shortest path length.
These results also address the question of Krioukov et al. whether there are efficient local routing protocols for the internet graph. There were promising experimental studies, but the question remained unsolved theoretically. Our results give for the first time a rigorous and analytical answer, assuming our random graph model.
Complex Systems Studies
My Recording – 161130_001
فایل صوتی سخنرانی دکتر سید ریحانی ک با عنوان "میکرودستکاری اجزای زیستی با لیزر" در مرکز تحقیقات بیوشیمی و بیوفیزیک دانشگاه تهران برگزار شد.
🌀 Statistical Thinking in Python (Part 1)
🚩 Course Description
After all of the hard work of acquiring data and getting them into a form you can work with, you ultimately want to make clear, succinct conclusions from them. This crucial last step of a data analysis pipeline hinges on the principles of statistical inference. In this course, you will start building the foundation you need to think statistically, to speak the language of your data, to understand what they are telling you. The foundations of statistical thinking took decades upon decades to build, but they can be grasped much faster today with the help of computers. With the power of Python-based tools, you will rapidly get up to speed and begin thinking statistically by the end of this course.
https://www.datacamp.com/courses/statistical-thinking-in-python-part-1
🌀 Statistical Thinking in Python (Part 2)
🚩 Course Description
After completing Statistical Thinking in Python (Part 1), you have the probabilistic mindset and foundational hacker stats skills to dive into data sets and extract useful information from them. In this course, you will do just that, expanding and honing your hacker stats toolbox to perform the two key tasks in statistical inference, parameter estimation and hypothesis testing. You will work with real data sets as you learn, culminating with analysis of measurements of the beaks of the Darwin's famous finches. You will emerge this course with new knowledge and lots of practice under your belt, ready to attack your own inference problems out in the world.
https://www.datacamp.com/courses/statistical-thinking-in-python-part-2
🚩 Course Description
After all of the hard work of acquiring data and getting them into a form you can work with, you ultimately want to make clear, succinct conclusions from them. This crucial last step of a data analysis pipeline hinges on the principles of statistical inference. In this course, you will start building the foundation you need to think statistically, to speak the language of your data, to understand what they are telling you. The foundations of statistical thinking took decades upon decades to build, but they can be grasped much faster today with the help of computers. With the power of Python-based tools, you will rapidly get up to speed and begin thinking statistically by the end of this course.
https://www.datacamp.com/courses/statistical-thinking-in-python-part-1
🌀 Statistical Thinking in Python (Part 2)
🚩 Course Description
After completing Statistical Thinking in Python (Part 1), you have the probabilistic mindset and foundational hacker stats skills to dive into data sets and extract useful information from them. In this course, you will do just that, expanding and honing your hacker stats toolbox to perform the two key tasks in statistical inference, parameter estimation and hypothesis testing. You will work with real data sets as you learn, culminating with analysis of measurements of the beaks of the Darwin's famous finches. You will emerge this course with new knowledge and lots of practice under your belt, ready to attack your own inference problems out in the world.
https://www.datacamp.com/courses/statistical-thinking-in-python-part-2
📄 Four lectures on probabilistic methods for data science
Roman Vershynin
🔗 https://arxiv.org/pdf/1612.06661v1
📌 ABSTRACT
Methods of high-dimensional probability play a central role in applications for statistics, signal processing theoretical computer science and related fields. These lectures present a sample of particularly useful tools of high-dimensional probability, focusing on the classical and matrix Bernstein's inequality and the uniform matrix deviation inequality. We illustrate these tools with applications for dimension reduction, network analysis, covariance estimation, matrix completion and sparse signal recovery. The lectures are geared towards beginning graduate students who have taken a rigorous course in probability but may not have any experience in data science applications.
Roman Vershynin
🔗 https://arxiv.org/pdf/1612.06661v1
📌 ABSTRACT
Methods of high-dimensional probability play a central role in applications for statistics, signal processing theoretical computer science and related fields. These lectures present a sample of particularly useful tools of high-dimensional probability, focusing on the classical and matrix Bernstein's inequality and the uniform matrix deviation inequality. We illustrate these tools with applications for dimension reduction, network analysis, covariance estimation, matrix completion and sparse signal recovery. The lectures are geared towards beginning graduate students who have taken a rigorous course in probability but may not have any experience in data science applications.
📄 Temporal profiles of avalanches on networks
James P Gleeson, Rick Durrett
🔗 https://arxiv.org/pdf/1612.06477v1
📌 ABSTRACT
An avalanche or cascade occurs when one event causes one or more subsequent events, which in turn may cause further events in a chain reaction. Avalanching dynamics are studied in many disciplines, with a recent focus on average avalanche shapes, i.e., the temporal profiles that characterize the growth and decay of avalanches of fixed duration. At the critical point of the dynamics the average avalanche shapes for different durations can be rescaled so that they collapse onto a single universal curve. We apply Markov branching process theory to derive a simple equation governing the average avalanche shape for cascade dynamics on networks. Analysis of the equation at criticality demonstrates that nonsymmetric average avalanche shapes (as observed in some experiments) occur for certain combinations of dynamics and network topology; specifically, on networks with heavy-tailed degree distributions. We give examples using numerical simulations of models of information spreading, neural dynamics, and threshold models of behaviour adoption.
James P Gleeson, Rick Durrett
🔗 https://arxiv.org/pdf/1612.06477v1
📌 ABSTRACT
An avalanche or cascade occurs when one event causes one or more subsequent events, which in turn may cause further events in a chain reaction. Avalanching dynamics are studied in many disciplines, with a recent focus on average avalanche shapes, i.e., the temporal profiles that characterize the growth and decay of avalanches of fixed duration. At the critical point of the dynamics the average avalanche shapes for different durations can be rescaled so that they collapse onto a single universal curve. We apply Markov branching process theory to derive a simple equation governing the average avalanche shape for cascade dynamics on networks. Analysis of the equation at criticality demonstrates that nonsymmetric average avalanche shapes (as observed in some experiments) occur for certain combinations of dynamics and network topology; specifically, on networks with heavy-tailed degree distributions. We give examples using numerical simulations of models of information spreading, neural dynamics, and threshold models of behaviour adoption.