Dynamic models of random simplicial complexes
Lead Research Organisation:
University of Birmingham
Department Name: School of Mathematics
Abstract
Networks have recently become a central notion in a variety of scientific disciplines such as computer science, data science, biology and economics. Their importance increased in the last decade as the development of the Internet and the mobile networks have had a significant impact on society and various sectors of the economy. This makes it important to develop an appropriate mathematical framework to understand their formation and evolution. In particular, it turns out that an intrinsic characteristic of network evolution is randomness. In fact, large networks involve randomess both in their formation and their evolution. One of the main challenges is to gain insight into how randomness actually gives rise to structure and self-organisation.
The most common representation of networks is through graphs, where the interaction between individuals is represented by an edge that joins the corresponding nodes. However, in reality interactions are far more complex and, in fact, involve a multitude of individuals. In this project, we will use the mathematical framework of random discrete topological spaces to develop a systematic theory of the evolution of networks whose growth is characterised by multidimensional interactions. Such spaces have also been used in an entirely different context, as part of the development of the theory of quantum gravity. There, they were used as an expression of the granular structure of space-time, in an attempt to unify general relativity with quantum mechanics.
In our project, we will consider even more general models which allow for dynamically growing structures. The objectives focus on the study of large-scale properties of these objects, based on tools and notions from combinatorics, probability theory and topology. Furthermore, we will explore how these features are linked to dynamics on these spaces, such as random walks and their mixing time. We will also determine the key combinatorial characteristics of these networks and investigate the emergence of global-scale phenomena in them. In particular, we will be aiming to determine those conditions on the growth mechanism which ensure the emergence of power-law degree distributions in the network as well as its small-world properties. Furthermore, we will aim to discover those conditions that characterise the emergence of condensation phenomena in these networks. Such phenomena are also relevant in statistical physics. In this context, they are linked to the emergence of irregularities in the distribution of the degrees and the existence of extremely highly connected nodes.
The most common representation of networks is through graphs, where the interaction between individuals is represented by an edge that joins the corresponding nodes. However, in reality interactions are far more complex and, in fact, involve a multitude of individuals. In this project, we will use the mathematical framework of random discrete topological spaces to develop a systematic theory of the evolution of networks whose growth is characterised by multidimensional interactions. Such spaces have also been used in an entirely different context, as part of the development of the theory of quantum gravity. There, they were used as an expression of the granular structure of space-time, in an attempt to unify general relativity with quantum mechanics.
In our project, we will consider even more general models which allow for dynamically growing structures. The objectives focus on the study of large-scale properties of these objects, based on tools and notions from combinatorics, probability theory and topology. Furthermore, we will explore how these features are linked to dynamics on these spaces, such as random walks and their mixing time. We will also determine the key combinatorial characteristics of these networks and investigate the emergence of global-scale phenomena in them. In particular, we will be aiming to determine those conditions on the growth mechanism which ensure the emergence of power-law degree distributions in the network as well as its small-world properties. Furthermore, we will aim to discover those conditions that characterise the emergence of condensation phenomena in these networks. Such phenomena are also relevant in statistical physics. In this context, they are linked to the emergence of irregularities in the distribution of the degrees and the existence of extremely highly connected nodes.
Planned Impact
The impact of this project is manifold and can be classified as follows.
Knowledge
- Scientific advances
The proposed research will significantly enhance the theoretical framework of random topological spaces and its applicability to the mathematical modelling of complex networks. This will be achieved through the development of dynamic probabilistic models of random topological spaces, whose formation mechanism is motivated by a fundamental class of models which are known as preferential attachment models. Our intention is to combine the topological notions with the methods of probabilistic combinatorics and probability theory in order to deduce the typical structural properties of these objects.
- Techniques
It is exactly the above combination that poses the main technical challenges of this project. The theory of random topological spaces as a natural ramification of the theory of random graphs is still at its infancy. The objectives of the present project demand the development of techniques for handling high dependencies in the evolution of networks which are multidimensional. To be more specific, this requires the asymptotic analysis of more involved Polya urn schemes than those that have been investigated so far. Furthermore, the objectives require the development of systematic techniques for the translation of topological notions into combinatorial objects which are amenable to probabilistic analysis.
Society and the Economy
The aim of network science is to bring together approaches from different scientific disciplines such as mathematics, physics, biology and computer science, in order to further develop a sound and rigorous theory of complex networks. This term describes the class of self-organising networks that emerge in a variety of settings such as human or human-made networks and biological networks. The theoretical understanding of these mechanisms of growth and formation will further shed a new light to our general understanding of network formation. This project aspires to contribute to this. This is not only a key issue in network science but it is also a fundamental aspect of the emerging area of data science. Having solid theoretical foundations which describe the growth of networks will in turn provide the foundations based on which data science will be able to develop algorithms and techniques for managing enormous sets of data. Thereby, it will help to underpin the infrastructure for various economic sectors that rely on data management.
People
The proposed project will enhance the combined research capacity of combinatorics, topology and probability, and it provides the platform for the career development of a postdoctoral research associate (PDRA) through a highly intra-disciplinary research theme. In addition to the direct involvement of the PDRA to the execution of the project, we will also pursue their broader professional as well as through relevant teaching activities, conference participation, research seminars and participation into summer schools, scientific visits as well as the organisation of scientific events. All these will ensure a multi-faceted skills development that meets the demand for experts both in industry and academia in areas that deal with the design and analysis of large networks.
Knowledge
- Scientific advances
The proposed research will significantly enhance the theoretical framework of random topological spaces and its applicability to the mathematical modelling of complex networks. This will be achieved through the development of dynamic probabilistic models of random topological spaces, whose formation mechanism is motivated by a fundamental class of models which are known as preferential attachment models. Our intention is to combine the topological notions with the methods of probabilistic combinatorics and probability theory in order to deduce the typical structural properties of these objects.
- Techniques
It is exactly the above combination that poses the main technical challenges of this project. The theory of random topological spaces as a natural ramification of the theory of random graphs is still at its infancy. The objectives of the present project demand the development of techniques for handling high dependencies in the evolution of networks which are multidimensional. To be more specific, this requires the asymptotic analysis of more involved Polya urn schemes than those that have been investigated so far. Furthermore, the objectives require the development of systematic techniques for the translation of topological notions into combinatorial objects which are amenable to probabilistic analysis.
Society and the Economy
The aim of network science is to bring together approaches from different scientific disciplines such as mathematics, physics, biology and computer science, in order to further develop a sound and rigorous theory of complex networks. This term describes the class of self-organising networks that emerge in a variety of settings such as human or human-made networks and biological networks. The theoretical understanding of these mechanisms of growth and formation will further shed a new light to our general understanding of network formation. This project aspires to contribute to this. This is not only a key issue in network science but it is also a fundamental aspect of the emerging area of data science. Having solid theoretical foundations which describe the growth of networks will in turn provide the foundations based on which data science will be able to develop algorithms and techniques for managing enormous sets of data. Thereby, it will help to underpin the infrastructure for various economic sectors that rely on data management.
People
The proposed project will enhance the combined research capacity of combinatorics, topology and probability, and it provides the platform for the career development of a postdoctoral research associate (PDRA) through a highly intra-disciplinary research theme. In addition to the direct involvement of the PDRA to the execution of the project, we will also pursue their broader professional as well as through relevant teaching activities, conference participation, research seminars and participation into summer schools, scientific visits as well as the organisation of scientific events. All these will ensure a multi-faceted skills development that meets the demand for experts both in industry and academia in areas that deal with the design and analysis of large networks.
Organisations
People |
ORCID iD |
| Nikolaos Fountoulakis (Principal Investigator) |
Publications
Chellig J
(2022)
Best response dynamics on random graphs
in Games and Economic Behavior
Fountoulakis N
(2019)
Dynamical Models for Random Simplicial Complexes
Fountoulakis N
(2022)
Dynamical models for random simplicial complexes
in The Annals of Applied Probability
Fountoulakis N
(2022)
Condensation phenomena in preferential attachment trees with neighbourhood influence
in Electronic Journal of Probability
Fountoulakis N
(2019)
High-dimensional bootstrap processes in evolving simplicial complexes
Fountoulakis N
(2021)
Algebraic and combinatorial expansion in random simplicial complexes
in Random Structures & Algorithms
Fountoulakis N
(2020)
Algebraic and combinatorial expansion in random simplicial complexes
Fountoulakis N.
(2022)
Algebraic and combinatorial expansion in random simplicial complexes
in Random Structures and Algorithms
Fountoulakis, N.
(2021)
Condensation phenomena in preferential attachment trees with neighbourhood influence
Przykucki M
(2020)
Smallest Percolating Sets in Bootstrap Percolation on Grids
in The Electronic Journal of Combinatorics
| Description | The aim of this project is to study preferential attachment models that are multidimensional. In a classical preferential attachment model, vertices form a network in which they arrive one-at-a-time and they select their neighbours according to their popularity. In this project, the aim to consider generalisations of this model where newly arriving vertices in the network select groups of other vertices. Such groups may indicate an existing relation between the members of the group (e.g. a collaboration). We use the concept of a simplicial complex to express this kind of multidimensional relations. Thus, when a new vertex arrives it joins one of the groups with probability proportional to some fitness function, associated with each group. The aspect of this family of models we explore has to do with the distribution of the degrees, that is, the number of neighbours a vertex has typically. Having degree distributions that belong to a certain class is a key feature of networks that appear in a wide range of applications. We have shown that the degree distribution of the multidimensional preferential attachment model belongs to this class. Moreover, we find a precise formula for the its determining parameter in terms of the parameters of the model. The other aspect of these models we considered is the evolution of epidemic processes on them. In the particular class of processes a node becomes infected if it belongs to at least a certain number of other groups each having at least one infected node. This process generalises a classic infection process which is called the bootstrap process. We determined a critical value for the density of initially infected nodes which leads to a complete infection. We further explored the condensation phenomena over evolving trees. Here, the evolution is determined by a preferential attachment mechanism which depends on the neighbourhood of vertices. That is, a vertex is more likely to be joined by a newly arriving vertex if its neighbourhood achieves a higher score that depends on the individual features of the vertices therein. In this sense, this evolution rule is 2-dimensional. We determined the conditions which ensure the emergence of condensation: that is, a positive fraction of the edges are attached to very few vertices. Thus, these vertices appear to be super-hubs inside the growing structure. Another aspect of this project had to do with the expansion properties and the spectrum of the combinatorial Laplace operator of a d-dimensional random simplicial complex. The model we considered is the standard model which generalises the classic binomial random graph. In particular, we consider face densities above the so-called cohomological connectivity threshold. This is a generalisation of the graph-theoretic notion of connectivity of the random graph (viewed as a 1-dimensional simplicial complex). Expander graphs have a variety of applications ranging from algebra to theoretical computer science. Here, we consider a high-dimensional notion of expansion and we explored its typical values on a standard model of a random simplicial complex. |
| Exploitation Route | These findings have been submitted for publication. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| URL | http://web.mat.bham.ac.uk/N.Fountoulakis/ |
| Description | This project aims to study models for networks that are evolving, and furthermore, their evolution is determined by a mechanism that is multidimensional. Classic models for evolving networks assume that when new individuals/nodes arrive, they select other individuals to connect to. We study extended mechanisms in which newcomers join groups of individuals. For example, in the network of scientific collaborations, there are groups of collaborators (e.g. though joint authorship of scientific papers) and when a new scientist joins this network, they become part of a group. So from that perspective, one can consider evolution mechanism that are multidimensional and consider such a network as a geometric evolving structure. In this project, we used the notion of a simplicial complex to express these multidimensional networks and developed a number of mathematical tools for the study of these models. |
| First Year Of Impact | 2021 |
| Sector | Other |
| Title | Measure-valued Poya processes |
| Description | This method provides a generalisation of the classical Polya urn model. In this simple stochastic model, an urn contains balls of various colours. At each round, a ball is selected uniformly at random and a ball of the same colour is added into the urn. In our case, the colours represent the composition of a simplex in an evolving simplicial complex. The classical setting does not apply in the case where the types a simplex can have may take arbitrary values in a continuum. To this purpose, we introduced the use of continuous generalisations of the classical Polya urn model in the analysis of our model. These are called measure-valued Polya processes. |
| Type Of Material | Improvements to research infrastructure |
| Year Produced | 2018 |
| Provided To Others? | No |
| Impact | We believe that this can become a standard tool in the analysis of the limiting behaviour of inhomogeneous evolving simplicial complexes. |
| Description | Large Networks and Random Graphs - Goethe- Universitat Frankfurt, Germany. |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I gave a presentation of our work on the degree distribution of evolving simplicial complexes. |
| Year(s) Of Engagement Activity | 2018 |
| URL | http://www.uni-frankfurt.de/72190960/Workshop-Info.pdf |