🔖 Random Multi-Hopper Model. Super-Fast Random Walks on Graphs
Ernesto Estrada, Jean-Charles Delvenne, Naomichi Hatano, José L. Mateos, Ralf Metzler, Alejandro P. Riascos, Michael T. Schaub
🔗 arxiv.org/pdf/1612.08631.pdf
📌 ABSTRACT
We develop a model for a random walker with long-range hops on general graphs. This random multi-hopper jumps from a node to any other node in the graph with a probability that decays as a function of the shortest-path distance between the two nodes. We consider here two decaying functions in the form of the Laplace and Mellin transforms of the shortest-path distances. Remarkably, when the parameters of these transforms approach zero asymptotically, the multi-hopper's hitting times between any two nodes in the graph converge to their minimum possible value, given by the hitting times of a normal random walker on a complete graph. Stated differently, for small parameter values the multi-hopper explores a general graph as fast as possible when compared to a random walker on a full graph. Using computational experiments we show that compared to the normal random walker, the multi-hopper indeed explores graphs with clusters or skewed degree distributions more efficiently for a large parameter range. We provide further computational evidence of the speed-up attained by the random multi-hopper model with respect to the normal random walker by studying deterministic, random and real-world networks.
Ernesto Estrada, Jean-Charles Delvenne, Naomichi Hatano, José L. Mateos, Ralf Metzler, Alejandro P. Riascos, Michael T. Schaub
🔗 arxiv.org/pdf/1612.08631.pdf
📌 ABSTRACT
We develop a model for a random walker with long-range hops on general graphs. This random multi-hopper jumps from a node to any other node in the graph with a probability that decays as a function of the shortest-path distance between the two nodes. We consider here two decaying functions in the form of the Laplace and Mellin transforms of the shortest-path distances. Remarkably, when the parameters of these transforms approach zero asymptotically, the multi-hopper's hitting times between any two nodes in the graph converge to their minimum possible value, given by the hitting times of a normal random walker on a complete graph. Stated differently, for small parameter values the multi-hopper explores a general graph as fast as possible when compared to a random walker on a full graph. Using computational experiments we show that compared to the normal random walker, the multi-hopper indeed explores graphs with clusters or skewed degree distributions more efficiently for a large parameter range. We provide further computational evidence of the speed-up attained by the random multi-hopper model with respect to the normal random walker by studying deterministic, random and real-world networks.
💻 Fundamentals of Machine Learning is NOW OPEN! Take this excellent tutorial here:
www.complexityexplorer.org/courses/81-fundamentals-of-machine-learning,
and read an interview with the instructors here:
https://www.complexityexplorer.org/news/85-what-s-so-special-about-fundamentals-of-machine-learning
www.complexityexplorer.org/courses/81-fundamentals-of-machine-learning,
and read an interview with the instructors here:
https://www.complexityexplorer.org/news/85-what-s-so-special-about-fundamentals-of-machine-learning
💻 Great profile about MIT math professor Philippe Rigollet. We have three courses of his on OCW:
Mathematics of Machine Learning:
https://ocw.mit.edu/courses/mathematics/18-657-mathematics-of-machine-learning-fall-2015/
High-Dimensional Statistics:
https://ocw.mit.edu/courses/mathematics/18-s997-high-dimensional-statistics-spring-2015/
Statistics for Applications:
https://ocw.mit.edu/courses/mathematics/18-650-statistics-for-applications-fall-2016/
Mathematics of Machine Learning:
https://ocw.mit.edu/courses/mathematics/18-657-mathematics-of-machine-learning-fall-2015/
High-Dimensional Statistics:
https://ocw.mit.edu/courses/mathematics/18-s997-high-dimensional-statistics-spring-2015/
Statistics for Applications:
https://ocw.mit.edu/courses/mathematics/18-650-statistics-for-applications-fall-2016/
MIT OpenCourseWare
Mathematics of Machine Learning | Mathematics | MIT OpenCourseWare
Broadly speaking, Machine Learning refers to the automated identification of patterns in data. As such it has been a fertile ground for new statistical and algorithmic developments. The purpose of this course is to provide a mathematically rigorous introduction…
💡 Complexity is not just a measure of how intricate, or sophisticated, something is. It defines the topology of information flow and of the processes which make Nature work!
🔗 https://resiliencepost.com/2018/01/16/on-the-extraordinary-importance-of-complexity/amp
#Complexity #Entropy #Energy #DNA #Nature
🔗 https://resiliencepost.com/2018/01/16/on-the-extraordinary-importance-of-complexity/amp
#Complexity #Entropy #Energy #DNA #Nature
The Resilience Post
On the extraordinary importance of complexity - The Resilience Post
Complexity is not just a measure of how intricate, or sophisticated, something is. Find out more about complexity in this text by Jacek Marczyk.
🔖 Markov Brains: A Technical Introduction
Arend Hintze, Jeffrey A. Edlund, Randal S. Olson, David B. Knoester, Jory Schossau, Larissa Albantakis, Ali Tehrani-Saleh, Peter Kvam, Leigh Sheneman, Heather Goldsby, Clifford Bohm, Christoph Adami
🔗 arxiv.org/pdf/1709.05601.pdf
📌 ABSTRACT
Markov Brains are a class of evolvable artificial neural networks (ANN). They differ from conventional ANNs in many aspects, but the key difference is that instead of a layered architecture, with each node performing the same function, Markov Brains are networks built from individual computational components. These computational components interact with each other, receive inputs from sensors, and control motor outputs. The function of the computational components, their connections to each other, as well as connections to sensors and motors are all subject to evolutionary optimization. Here we describe in detail how a Markov Brain works, what techniques can be used to study them, and how they can be evolved.
Arend Hintze, Jeffrey A. Edlund, Randal S. Olson, David B. Knoester, Jory Schossau, Larissa Albantakis, Ali Tehrani-Saleh, Peter Kvam, Leigh Sheneman, Heather Goldsby, Clifford Bohm, Christoph Adami
🔗 arxiv.org/pdf/1709.05601.pdf
📌 ABSTRACT
Markov Brains are a class of evolvable artificial neural networks (ANN). They differ from conventional ANNs in many aspects, but the key difference is that instead of a layered architecture, with each node performing the same function, Markov Brains are networks built from individual computational components. These computational components interact with each other, receive inputs from sensors, and control motor outputs. The function of the computational components, their connections to each other, as well as connections to sensors and motors are all subject to evolutionary optimization. Here we describe in detail how a Markov Brain works, what techniques can be used to study them, and how they can be evolved.
This media is not supported in your browser
VIEW IN TELEGRAM
Using Self-Organizing Maps to solve the Traveling Salesman Problem https://t.co/2KkTgcGDaY & https://t.co/5frWZeK056 https://t.co/nmYIrTBGsq
Complex Systems Studies
Using Self-Organizing Maps to solve the Traveling Salesman Problem https://t.co/2KkTgcGDaY & https://t.co/5frWZeK056 https://t.co/nmYIrTBGsq
Diego Vicente
Using Self-Organizing Maps to solve the Traveling Salesman Problem
Using Self-Organizing Maps to solve the Traveling Salesman Problem The Traveling Salesman Problem is a well known challenge in Computer Science: it consists on finding the shortest route possible that traverses all cities in a given map only once. Although…
❄️ Nice article about extreme difficulty most people have understanding p-values. Even worse: confidence intervals. And most statisticians don't even compute p-values very accurately except for the simplest models.
https://fivethirtyeight.com/features/not-even-scientists-can-easily-explain-p-values/amp/
https://fivethirtyeight.com/features/not-even-scientists-can-easily-explain-p-values/amp/
FiveThirtyEight
Not Even Scientists Can Easily Explain P-values
P-values have taken quite a beating lately. These widely used and commonly misapplied statistics have been blamed for giving a veneer of legitimacy to dodgy stu…
🔖 Tracking Network Dynamics: a review of distances and similarity metrics
Claire Donnat, Susan Holmes
🔗 arxiv.org/pdf/1801.07351.pdf
📌 ABSTRACT
From longitudinal biomedical studies to social networks, graphs have emerged as a powerful framework for describing evolving interactions between agents in complex systems. In such studies, the data typically consists of a set of graphs representing a system's state at different points in time or space. The analysis of the system's dynamics depends on the selection of the appropriate tools. In particular, after specifying properties characterizing similarities between states, a critical step lies in the choice of a distance capable of reflecting such similarities. While the literature offers a number of distances that one could a priori choose from, their properties have been little investigated and no guidelines regarding the choice of such a distance have yet been provided. However, these distances' sensitivity to perturbations in the network's structure and their ability to identify important changes are crucial to the analysis, making the selection of an adequate metric a decisive -- yet delicate -- practical matter.
In the spirit of Goldenberg, Zheng and Fienberg's seminal 2009 review, the purpose of this article is to provide an overview of commonly-used graph distances and an explicit characterization of the structural changes that they are best able to capture. To see how this translates in real-life situations, we use as a guiding thread to our discussion the application of these distances to the analysis a longitudinal microbiome study -- as well as on synthetic examples. Having unveiled some of traditional distances' shortcomings, we also suggest alternative similarity metrics and highlight their relative advantages in specific analysis scenarios. Above all, we provide some guidance for choosing one distance over another in certain types of applications. Finally, we show an application of these different distances to a network created from worldwide recipes.
Claire Donnat, Susan Holmes
🔗 arxiv.org/pdf/1801.07351.pdf
📌 ABSTRACT
From longitudinal biomedical studies to social networks, graphs have emerged as a powerful framework for describing evolving interactions between agents in complex systems. In such studies, the data typically consists of a set of graphs representing a system's state at different points in time or space. The analysis of the system's dynamics depends on the selection of the appropriate tools. In particular, after specifying properties characterizing similarities between states, a critical step lies in the choice of a distance capable of reflecting such similarities. While the literature offers a number of distances that one could a priori choose from, their properties have been little investigated and no guidelines regarding the choice of such a distance have yet been provided. However, these distances' sensitivity to perturbations in the network's structure and their ability to identify important changes are crucial to the analysis, making the selection of an adequate metric a decisive -- yet delicate -- practical matter.
In the spirit of Goldenberg, Zheng and Fienberg's seminal 2009 review, the purpose of this article is to provide an overview of commonly-used graph distances and an explicit characterization of the structural changes that they are best able to capture. To see how this translates in real-life situations, we use as a guiding thread to our discussion the application of these distances to the analysis a longitudinal microbiome study -- as well as on synthetic examples. Having unveiled some of traditional distances' shortcomings, we also suggest alternative similarity metrics and highlight their relative advantages in specific analysis scenarios. Above all, we provide some guidance for choosing one distance over another in certain types of applications. Finally, we show an application of these different distances to a network created from worldwide recipes.
🔖 A General Definition of Network Communities and the Corresponding Detection Algorithm
Haoye Lu, Amiya Nayak
🔗 arxiv.org/pdf/1801.07783.pdf
📌 ABSTRACT
Network structures, consisting of nodes and edges, have applications in almost all subjects. The sets of nodes strongly connected internally are called communities. Industries (including cell phone carriers and online social media companies) need community structures to allocate network resources and provide proper customer services. However, all community detection methods are motivated by solving some concrete problems, while the applicabilities in other fields are open to question. Therefore, confronting a new community problem, researchers need to derive algorithms ad hoc, which is time-consuming and even unnecessary. In this paper, we represent a general procedure to find community structures in concrete problems. We mainly focus on two typical types of networks: transmission networks and similarity networks. We reduce them to a unified graph model, based on which we propose a general method to define and detect communities. Readers can specialize our general algorithm to accommodate their problems. In the end, we also give a demonstration to show how the algorithm works.
Haoye Lu, Amiya Nayak
🔗 arxiv.org/pdf/1801.07783.pdf
📌 ABSTRACT
Network structures, consisting of nodes and edges, have applications in almost all subjects. The sets of nodes strongly connected internally are called communities. Industries (including cell phone carriers and online social media companies) need community structures to allocate network resources and provide proper customer services. However, all community detection methods are motivated by solving some concrete problems, while the applicabilities in other fields are open to question. Therefore, confronting a new community problem, researchers need to derive algorithms ad hoc, which is time-consuming and even unnecessary. In this paper, we represent a general procedure to find community structures in concrete problems. We mainly focus on two typical types of networks: transmission networks and similarity networks. We reduce them to a unified graph model, based on which we propose a general method to define and detect communities. Readers can specialize our general algorithm to accommodate their problems. In the end, we also give a demonstration to show how the algorithm works.
Deep learning for real-time gravitational wave detection and parameter estimation: Results with advanced LIGO data
https://www.sciencedirect.com/science/article/pii/S0370269317310390
https://www.sciencedirect.com/science/article/pii/S0370269317310390
🔖 Correlations and dynamics of consumption patterns in social-economic networks
Yannick Leo, Márton Karsai, Carlos Sarraute, Eric Fleury
🔗 arxiv.org/pdf/1801.08856.pdf
📌 ABSTRACT
We analyse a coupled dataset collecting the mobile phone communications and bank transactions history of a large number of individuals living in a Latin American country. After mapping the social structure and introducing indicators of socioeconomic status, demographic features, and purchasing habits of individuals we show that typical consumption patterns are strongly correlated with identified socioeconomic classes leading to patterns of stratification in the social structure. In addition we measure correlations between merchant categories and introduce a correlation network, which emerges with a meaningful community structure. We detect multivariate relations between merchant categories and show correlations in purchasing habits of individuals. Finally, by analysing individual consumption histories, we detect dynamical patterns in purchase behaviour and their correlations with the socioeconomic status, demographic characters and the egocentric social network of individuals. Our work provides novel and detailed insight into the relations between social and consuming behaviour with potential applications in resource allocation, marketing, and recommendation system design.
https://t.co/h2kl2pQhDV
Yannick Leo, Márton Karsai, Carlos Sarraute, Eric Fleury
🔗 arxiv.org/pdf/1801.08856.pdf
📌 ABSTRACT
We analyse a coupled dataset collecting the mobile phone communications and bank transactions history of a large number of individuals living in a Latin American country. After mapping the social structure and introducing indicators of socioeconomic status, demographic features, and purchasing habits of individuals we show that typical consumption patterns are strongly correlated with identified socioeconomic classes leading to patterns of stratification in the social structure. In addition we measure correlations between merchant categories and introduce a correlation network, which emerges with a meaningful community structure. We detect multivariate relations between merchant categories and show correlations in purchasing habits of individuals. Finally, by analysing individual consumption histories, we detect dynamical patterns in purchase behaviour and their correlations with the socioeconomic status, demographic characters and the egocentric social network of individuals. Our work provides novel and detailed insight into the relations between social and consuming behaviour with potential applications in resource allocation, marketing, and recommendation system design.
https://t.co/h2kl2pQhDV
Twitter
Alessandro Vespignani
Correlations and dynamics of consumption patterns in social-economic networks https://t.co/ybrqLPYGFA
💡 Networks, Crowds, and Markets: Reasoning About a Highly Connected World
By David Easley and Jon Kleinberg
http://www.cs.cornell.edu/home/kleinber/networks-book/
By David Easley and Jon Kleinberg
http://www.cs.cornell.edu/home/kleinber/networks-book/
🔅 The Shallowness of Google Translate
The program uses state-of-the-art AI techniques, but simple tests show that it's a long way from real understanding.
https://www.theatlantic.com/amp/article/551570/
The program uses state-of-the-art AI techniques, but simple tests show that it's a long way from real understanding.
https://www.theatlantic.com/amp/article/551570/