Core Decomposition Spectra of Large Graphs and their Applications in Modelling

H. Fuks and M. Krzeminski (Canada)


Mathematical modelling, complex networks, core decom position, language modelling


Systems with large number of interacting components are often modelled by random graphs and networks. In mod els of this type, one frequently needs to characterize graph clustering at both local and global level. We propose a method of characterization of clustering in large graphs and networks using the concept of k-core decomposition. The plot of clustering coefficient of k-core versus size of k-core will be called the spectrum of clustering coefficients. We show that k-core spectrum may play an important role in language graphs, such as graphs constructed from language dictionaries, where it can be used to describe some dynam ical phenomena by purely static, topological quantities. In the last part of the paper, we propose a random graph model of a dictionary graph for which the k-core spectrum has similar features as in real dictionary graphs. The model is based on generalization of geometric random graphs in which the range parameter varies from vertex to vertex.

Important Links:

Go Back