
BMe Research Grant 

My research interest is focused on Internetrelated mathematical questions, most importantly, on the theory of different network models. Our aim is to describe and present network models that share properties similar to many of the most important real networks, like ones with hierarchical structure combined with scalefree degree distribution, or those consisting of small, wellwired communities connected by weak edges. These and similar models gain high interest in both the mathematical and applied sciences.
The research takes place at the the Department of Stochastics of BME, which is considered the strongest Central European research place in the field of probability and stochastics. Our professors, Domokos Szász (vice president of the Hungarian Academy of Sciences, dynamical systems), Bálint Tóth, (head of department, longmemory random walks) and Károly Simon (random and deterministic fractals) publish in the best reputed journals and are plenary speakers of conferences of the field. The younger generation is represented by internationally recognized researchers like Márton Balázs (interacting particle systems), Péter Tóth (dynamical systems) and Balázs Székely (applied probability). An outstanding probability seminar held in Hungary, the Stochastic Seminar attracts the most prestigious researchers to give lectures. A most important strength of our department is the high rate of excellent young researchers brought up here during the last decade. Most of the graduate students are offered postdoctoral positions at leading universities in the USA or in Europe after PhD and become successful researchers.
Five institutes (including the Math Institute at BME) have won a consortial project (filed with OTKA NKTH no. 77778) for the research of future Internet. The leader of the project is professor Károly Simon. My research aims at providing new results in the field of Internet related mathematical questions. Since this area is new at our department, it was (and still is) very important for us to establish and maintain connections with leading Hungarian and foreign research groups in the field. I have spent three months at the Theory Group of Microsoft Research, working with Yuval Peres – two joint papers are in process. We also collaborated with Anna Karlin, (University of Washington), and this work yielded topics for MSc and BSc thesis of our students. We also started a joint work on the modeling of communities in social networks with professor Béla Bollobás, one of the most famous researcher of the mathematics of random graphs. As a starting point of this joint work served the social network models of János Kertész (BME, Institute of Physics, complex networks). We also contacted Tamás Vicsek (ELTE). The paper [A] where we generalized the deterministic scalefree network model he and his coauthors introduced in [1] has been accepted by Chaos, Solitons and Fractals and will be published soon. I present the content of this paper below.
In the last two decades, a considerable amount of attention have been paid to the study
of complex networks like the World Wide Web, social networks, or
biological networks.
This resulted in the construction of
numerous network models, which try to model different properties of real
networks.
An important feature in most real networks is the scalefree property,
i.e., for a randomly chosen vertex in the graph, the number of edges starting
from the node has distribution with
power law decay. This means that high proportion of the vertices have very small
degree but there are also some vertices which have enormously many edges. Most
models having this property use a version of preferential
attachment and are of probabilistic nature. A completely different approach
was initiated by Barabási, Ravasz and Vicsek [1]. The
deterministic network models they introduced were generated by a
method commonly used in constructing fractals. Their models
exhibit hierarchical structure and the degree sequence obeys power law decay with exponent 1+log3/log2. To model the clustering
behavior of real networks as well, Ravasz and Barabási [2]
enhanced the original model so that their deterministic network model preserved the same power law decay and features a
clustering behavior similar to many real networks. Namely, the
average local clustering coefficient is independent of the size of the
network and the local clustering coefficient decays inversely
proportional to the degree of the node.
In our research we aimed to generalize
the model in the sense that we generate a graph sequence with hierarchical
structure obeying power law degree distribution with exponent γ,
which can be arbitrary in a given range. (An interesting case is the modeling of
networks with γ between 1 and 2, where the expected value of degree
distribution tends to infinity.) Another goal was to
randomize the model and produce random graphs with closelyhierarchical
structure with a given power law exponent.
We also aimed to give
mathematically rigorous proofs of statements about graphtheoretical properties
of the network (average shortest path, diameter, behavior of local clustering
coefficient as the function of the degree of the given node).
After appropriate coding the vertices of the graph, we mapped
the adjacency matrix of the
graphs in the unit square (see the picture below) and then
we proved convergence of this embedding. (In the picture
below, each colored square corresponds to an edge of the same color in the
picture above). We showed that this sequence of sets converges to the
attractor of a graphdirected self similar set. The geometrical properties of
the set are characterized by the corresponding iterated function
system.
So, we translated the graph sequence into the language of
fractals: the hierarchical structure corresponds to the fact that the next set
consist of little copies of the previous set, positioned in the diagonal of the
unit square. The edges connecting different copies are in the offdiagonal domain and
are converging to a selfsimilar fractal.
With this new
description we managed to generate hierarchical graph sequences starting from
arbitrary bipartite graph, and to derive their properties from the coding of
vertices and from the fractal.
Starting from any
bipartite graph, we can define the corresponding hierarchical graph sequence
(an example can be seen in the figure on the right). The
power law exponent of the degree distribution can be determined from the initial
graph, or from the Hausdorff dimension
of the fractal coming from the embedded adjacency matrix in the unit square:
It is most interesting if the initial graph
has more edges than vertices. We proved that in this case the exponent γ is a quotient: the numerator is the Hausdorff dimension of the
intersection of the fractal with a line randomly thrown through it, and the
denominator is the Hausdorff dimension of the intersection of the fractal with a
vertical line. (see the picture below).
Using the appropriate coding of vertices we proved that the diameter of
the graph is proportional to the logarithm of the number of vertices.
Additionally, we showed that the expected length of the shortest path between two
random vertices is of the same order. Considering the slightly modified version
of the model we proved that the local clustering coefficient of any vertex is
proportional to 1/degree of the node, which is a rigorous proof of argumentations based on simulation
results.
Finally, we randomized the
model, which randomization can be described by the following probabilistic
interpretation: Imagine a deterministic graph sequence, where each node is replaced by an urn. Now take a number of balls, so that every urn receive on average as many balls as the number of vertices in the initial smallest graph. Drop
these balls independently and uniformly at random into the urns. In our random
graph each vertex corresponds to a ball, and two vertices are connected by an
edge if the corresponding balls landed in urns connected in the deterministic
graph. We proved that the random graph sequence we get by this method shares the
same power law exponent γ as the deterministic one.
Publications
[A] J. Komjáthy, K. Simon. Generating hierarchical scalefree graphs from fractals. Chaos, Solitons & Fractals (2011), doi:10.1016/j.chaos.2011.05.012
[B] J. Komjáthy, J. Miller, Y. Peres. A tight bound of the uniform mixing
time of lamplighter walks. In preparation.
Links
Department of Stochastics, BME
Microsoft Research,
Theory Group
Complex Networks
Research Group, Department of Theoretical Physics, BME
References
[1] A.L. Barabási, E. Ravasz, T. Vicsek, Deterministic ScaleFree Networks. Physica A: Statistical Mechanics and its Applications 299, Issues 34 559–564 (2001) 559–564.
[2] E. Ravasz, A.L. Barabási. Hierarchical organization in complex networks. Phys.Rev. E 67 (2003) 47 026112.
[3] B. Bollobás. Random graphs. Cambridge University Press,
2001.