Complex Network Generative Models Using Corona Product of Graphs
Loading...
Date
2017-11
Researcher
Sharma, Rohan
Supervisor
Adhikari, Bibhas
Journal Title
Journal ISSN
Volume Title
Publisher
Indian Institute of Technology Jodhpur
Abstract
Complex networks are ubiquitous in natural, technological and social systems. In this thesis, we propose complex network generative models based on corona product of two graphs. A major feature of this framework is that it gives a visual understanding of the network generation process which helps in deriving many properties of the resulting networks analytically. We propose four network generative models among which two models are deterministic and we call them corona graphs and self-organized corona graphs (SoCG). Both of these models are defined by a network motif. Indeed, corona graphs are defined by taking the corona product of a network motif with itself iteratively. The network motif which defines a resulting corona graph, is called the seed graph for the corona graph. We investigate certain structural properties of corona graphs including degree distribution, diameter, and node betweenness distribution. We also derive computable expressions for eigenvalues, Laplacian eigenvalues and signless Laplacian eigenvalues of corona graphs defined by certain seed graphs. It is observed that the cumulative degree distribution of a corona graph decays exponentially when a large number of iterations is considered to generate the corona graph. This observation conveys a limitation of corona graphs in employing them as practical models for many real networks since a real network often exhibits power-law in the tail of its degree distribution. Thus we define a self-organization process for link generation in each step of the generation of a corona graph in addition to the links defined by the corona product itself. This provides a new network generative model which we call self-organized corona graphs (SoCG). We observe that SoCG inherit a hierarchical pattern in its structure and the degree distribution follows power-law in its tail when a large number of iterations is considered. In addition, we investigate the diameter and clustering coefficient of SoCG which establish that SoCG are small world and SoCG have high clustering coefficients for certain seed graphs. Obviously, large SoCG inherit a motif which is the seed graph itself. We compare the spectral radii and algebraic connectivities of SoCG with that of corona graphs using numerical simulation. We also analyse the count of different network motifs that are inherited by large SoCG defined by certain seed graphs. The next model which we propose in this thesis is called generalized corona graphs defined by Erd ¨ os-R ´ enyi graphs (GCG-ER). This model is inspired by exploring the idea of corona graphs defined by Erd ¨ os-R ´ enyi (ER) graphs. Here, we consider a simple connected graph on n 2 nodes initially and the definition of generalized corona product of graphs is employed to add ER graphs (having n nodes) with the existing nodes, picked randomly where all such ER graphs have a fixed edge probability. We continue the process iteratively and hence generate a large network. Thus, in GCG-ER, the deterministic links are generated due to the definition of generalized corona product of graphs, and links with a fixed link-probability are introduced due to the addition of ER graphs in each step of the generation of the resulting network. We investigate certain structural properties of these graphs that include degree distribution, average path length, node betweenness distribution, expected number of triangles and the average clustering coefficient. Finally, we propose a stochastic model for generation of complex networks inspired by the generalized corona product of graphs and we call the resulting graphs as stochastic corona graphs (SCG). First we define generalized stochastic corona product of graphs and use it to define SCG in which existence of all the possible edges are defined with a fixed probability. This model can also be explained as GCG-ER in which the deterministic links and the initial deterministic connected graph in GCG-ER are converted as links with a fixed probability, say p; and an ER graph with edge-probability p respectively. We also demonstrate a social perspective for formation of these graphs. We investigate the degree distribution, expected number of triangles and the average clustering coefficient of these graphs.
Description
Keywords
Citation
Sharma, Rohan.(2018). Complex network generative models using corona product of graphs (Doctor's thesis). Indian Institute of Technology Jodhpur, Jodhpur.