Theses

Permanent URI for this community

https://ir.iitj.ac.in/handle/123456789/4

Browse

Browsing Theses by Supervisor "Adhikari, Bibhas"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Complex Network Generative Models Using Corona Product of Graphs
    (Indian Institute of Technology Jodhpur, 2017-11) Adhikari, Bibhas
    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.
  • Thumbnail Image
    Item
    A Measure of Balance, Spectra of Signed Graphs, and Novel Algorithm for Matrix Determinant and Parmanent
    (Indian Institute of Technology Jodhpur, 2018-07) Adhikari, Bibhas
    Signed graphs are imperative to represent a system where the affinity and aversion co-exist between its entities. In a signed graph, any edge is either positive or negative. A positive edge reflects the existence of affinity between two vertices while a negative edge reflects the existence of aversion. Strong balance is a key concept in signed graphs which gives the notion of stability and structure in it. A cycle in a signed graph is called strongly balanced when it has an even number of negative edges. A signed graph is called strongly balanced graph when all of its cycles are strongly balanced. A slight generalization of strong balance is the concept of weak balance. According to this concept, all the cycles in a signed graph are weakly balanced except those which have only one negative edge. A signed graph is called weakly balanced when all of its cycles are weakly balanced. An interesting thing about a strongly balanced signed graph is that it can be partitioned into two parts of vertices such that all the edges inside any part are positive and all the edges between these parts are negative. Also, a signed graph is strongly balanced if and only if its eigenvalues are equal to the eigenvalues of its underlying unsigned graph. But what if some of the cycles of signed graphs are not strongly balanced? This gives rise to the concept of degree of unbalance. There are measures of the degree of unbalance with conflicting results. The importance of these measures lies in the fact that they are being used for (i) distinguishing two signed graphs based upon their degree of unbalance, (ii) the sign prediction of the edges. The eigenvalues of signed graphs can play a major role in defining a measure for the degree of unbalance. In an attempt towards developing a reasonable measure of the degree of unbalance, we first give a measure of the degree of unbalance using eigenvalue of signed graphs. Later we used this measure for sign prediction in signed graphs. We propose a parametrized walk based measure for lack of balance in signed networks inspired by the Katz measure of similarity of two vertices in a network. The proposed measure can be used to distinguish signed social networks on the basis of their degree of lack of balance. Further, the Katz prediction rule is exploited to derive that the cycles of shorter lengths can predict the sign of an edge in certain popular empirical signed social networks better than the longer cycles. Similar to strongly balanced signed graphs, the vertex set of a weakly balanced graph can be partitioned into more than two parts such that all the edges inside any part are positive and all the edges between any two parts are negative. Finding spectral criteria for the weak balance is still an open problem. However, we have found the characteristic polynomial and hence the spectra of some weakly balanced graphs induced from the complete graph. There is an interplay between signed digraphs and eigenvalues, determinant, permanent of matrices. Every square matrix can be represented as a weighted signed digraph. The structure of the signed digraph can be exploited to give some interesting matrix theoretical results. Using the blocks in digraphs we define a new partition, that we call as B-partition. The characteristic and permanent polynomial of a matrix can be elegantly calculated using B-partitions of the corresponding digraph. Similarly, the determinant and the permanent of a matrix can be obtained. Later, we analyzed the parametrized complexity of this developed method for the determinant and permanent. For a class of matrices, the complexity of developed method beats the state of art complexities.
  • Thumbnail Image
    Item
    Parametric network models, network reconstruction and diffusion protocols for networks
    (Indian Institute of Technology Jodhpur, 2018-03) Adhikari, Bibhas; Mazumdar, Mainak; Badarla, Venkata Ramana
    In this thesis we propose parametric network models for generation of complex networks that can inherit statistical properties of real networks. The models are based on different growth processes that are observed in different social contexts, for example, preferential attachment, random attachment with local growth. The chemical process, known as nucleation is investigated as a network formation process and thus a network model is proposed inspired by nucleation. Further, the parametric model approach for generation of networks is extended and employed in to solving the problem of structural reconstruction of real scale-free networks. In this attempt, a 2-parameter network generation model, called Network-Reconstruction-Model (NRM) is developed. A reconstruction technique is introduced to reconstruct a given real scale-free network by finding optimal values of the model parameters, utilizing the power-law exponent of the degree distribution of the real network, such that the corresponding model network inherit multiple structural properties of the real network. The performance of all the models in order to inherit properties of real networks is tested with different examples of real networks. The efficiency of NRM and the proposed reconstruction technique in order to solve the structural reconstruction problem are compared with some existing network models. Preferential attachment is one of the well known procedures that has been considered in literature to explain the existence of power-law in the degree distribution of real networks. However, often a diffusion process on a network influences the structural organization of the network and vice versa. Thus a natural question is: How do the structural dynamics and diffusion dynamics interact each other so that power-law in degree distribution arise or sustain in a network? This is thoroughly investigated in the thesis by introducing continuous and discontinuous truncated biased random walks on networks, where the diffusion process is considered as a random walk dynamics on the network. These proposed random walk dynamics could justify preferential growth of networks. Moreover, a diffusion protocol is proposed that can help detecting structural irregularities in static and dynamic networks, for example, the phenomena of link failure. Finally, a framework is proposed to identify existence of links in a network by investigating datasets of Susceptible-Infected-Susceptible (SIS) diffusion dynamics on networks.