Simplicial complexes and complex networks

Abstract

In modern theoretical physics (quantum gravity, computational electromagnetism, gauge theories, elasticity, to name a few) simplicial complexes have become an important objects due to their computational convenience and power of algebraic topological concepts. On the other hand, physics (and mathematics) of complex systems formed by the large number of elements interacting through pairwise interactions in highly irregular manner, is the most commonly restricted to concepts and methods of the graph theory. Such systems are called complex networks and notions of graph and complex network are used interchangeably. The achievements of the complex networks research are important for modern world and largely reshape our notion of a large class of complex phenomena, primarily because seemingly random and disorganized phenomena display meaningful structure and organization. The same stands also for the aggregations of complex network’s elements into communities (modules or clusters), which as a major drawback has that they are restricted to the collections of pairwise interactions. In this thesis to the notions of structure and substructure of complex systems, exemplified by complex networks, are given a new meaning through the changing the notion of community, by defining a simplicial community. Unlike the common notion of community, simplicial community is characterized by higher-order aggregations of complex network’s elements. Namely, starting from typical properties of complex systems it was shown that the natural substructure of complex networks emerges like the aggregations of a multidimensional simplices. It was further shown that simplicial complexes may be constructed from complex networks in several different ways, indicating the possible different hidden organizational patterns leading to the final structure of complex network and which are responsible for the network properties. In this thesis two simplicial complexes obtained from complex networks are studied: the neighborhood and the clique complex. Relying on the combinatorial algebraic topology concepts a unified mathematical framework for the study of their properties is proposed. The topological quantities, like structure vectors, Betti numbers, combinatorial Laplacian operator are calculated for diverse models real-world networks. Properties of spectra of combinatorial iii Laplacian operator of simplicial complexes are explored, and the necessity of higher order spectral analysis is discussed and compared with results for ordinary graphs...

U savremenoj teorijskoj fizici (na primer, kvantnoj gravitaciji, raˇcunskom elektromagnetizmu, gejdˇz teoriji, elastiˇcnosti) simplicijalni kompleksi su postali vaˇzni objekti zbog njihove raˇcunske pogodnosti i mo´ci koncepata algebarske topologije. Sa druge strane, fizika (i matematika) kompleksnih sistema formiranih od velikog broja elemenata koji interaguju parnim interakcijama na izrazito neregularan naˇcin, najˇceˇs´ce je ograniˇcena na koncepte i metode teorije grafova. Takvi sistemi se nazivaju kompleksne mreˇze i pojmovi graf i kompleksna mreˇza se poistove´cuju. Doprinosi istraˇzivanja kompleksnih mreˇza su vaˇzni za savremeni svet i umnogome preoblikuju naˇse poimanje velike klase kompleksnih fenomena, pre svega zbog toga ˇsto naizgled sluˇcajni i neured-eni fenomeni pokazuju smislenu strukturu i organizaciju. Isto vaˇzi i za agregacije elemenata kompleksne mreˇze u zajednice (module ili klastere), koje kao najve´ci nedostatak imaju osobinu da su ograniˇcene na kolekcije parnih interakcija. U ovoj tezi pojmovima strukture i podstrukture kompleksnog sistema, kroz primer kompleksne mreˇze, dato je novo znaˇcenje menjanjem pojma zajednice, definisanjem simplicijalne zajednice. Za razliku od uobiˇcajenog pojma zajednice, simplicijalna zajednica je karakterisana sa agregacijama viˇseg reda elemenata mreˇze. Naime, poˇsavˇsi od tipiˇcnih osobina kompleksnih sistema pokazano je da se kao prirodna podstruktura kompleksne mreˇze pojavljuju agregacije multidimenzionalnih simpleksa. Pokazano je, dalje, da se simplicijalni kompleksi mogu iz kompleksnih mreˇza konstruisati na nekoliko razliˇcitih naˇcina, ukazuju´ci na postojanje razliˇcitih skrivenih organizacionih obrazaca koji vode do konaˇcne strukture kompleksne mreˇze i koji su odgovorni za osobine mreˇze. U ovoj tezi su razmatrana dva simplicijalna kompleksa dobijena iz kompleksne mreˇze: kompleks susedstva i klika kompleks. Oslanjaju´ci se na koncepte kombinatorijalne algebarske topologije predloˇzen je objedinjeni matematiˇcki okvir za prouˇcavanje njihovih osobina. Topoloˇske veliˇcine, kao ˇsto su strukturni vektori, Betti brojevi, operator kombinatorni laplasijan, raˇcunate su za razliˇcite modele realnih mreˇza. Ispitivane su osobine spektra operatora kombinatorni laplasijan simplicijalnog kompleksa, i razmatrana je neophodnost spektralne analize viˇseg reda koja je pored-ena sa rezultatima za obiˇcne grafove...