Search

In recent years, complex network research which is multidisciplinary by nature is very popular as it is a valuable tool for analysing complex real-world systems. These systems are usually studied in a large-scale data structure where they show different kinds of non-trivial topological structural properties. Since realworld systems are sometimes too large to describe explicitly, various network models have been developed to mimic their construction processes. While most of the tools used to study their structural properties are coming from graph theory, spectral analysis is another method that can be used to reveal the structural inheritance properties of a network. In this dissertation, we focus on the studies for normalised Laplacian spectrum on six different undirected and directed network models namely, Erdos-Rényi (ER), Watts-Strogatz (WS), Barabási-Albert (BA), square grid ((Sgrid, triangular grid (Tgrid) and growing geometrical network (GGN) network models. These network models are manipulated and constructed using Mathematica software. Spectral graph theory is used to study the network properties by utilising eigenvalues associated with the normalised Laplacian matrix computed via eigendecomposition method. Spectral measures such as spectral density plot, Cheeger constant, discrepancy and energy have been performed to analyse the directed and undirected network models. The spectral plot for the undirected and directed networks showed very different patterns. Most of the directed network models showed a very sharp peak at eigenvalue 1 while for the undirected networks only ER, BA and Sgrid show this feature. Undirected Tgrid plots have two peaks, one is at 1 and another is in between {1, 1.5} while GGN has a sharp peak at 1.5 and followed by a smaller peak between {1, 1.5}. These patterns are usually unique and depend on the network itself. Network motifs have been utilized to analyse the topological structure of these networks. It is found that ER network

In recent years, complex network research which is multidisciplinary by nature is very popular as it is a valuable tool for analysing complex real-world systems. These systems are usually studied in a large-scale data structure where they show different kinds of non-trivial topological structural properties. Since realworld systems are sometimes too large to describe explicitly, various network models have been developed to mimic their construction processes. While most of the tools used to study their structural properties are coming from graph theory, spectral analysis is another method that can be used to reveal the structural inheritance properties of a network. In this dissertation, we focus on the studies for normalised Laplacian spectrum on six different undirected and directed network models namely, Erdos-Rényi (ER), Watts-Strogatz (WS), Barabási-Albert (BA), square grid ((Sgrid, triangular grid (Tgrid) and growing geometrical network (GGN) network models. These network models are manipulated and constructed using Mathematica software. Spectral graph theory is used to study the network properties by utilising eigenvalues associated with the normalised Laplacian matrix computed via eigendecomposition method. Spectral measures such as spectral density plot, Cheeger constant, discrepancy and energy have been performed to analyse the directed and undirected network models. The spectral plot for the undirected and directed networks showed very different patterns. Most of the directed network models showed a very sharp peak at eigenvalue 1 while for the undirected networks only ER, BA and Sgrid show this feature. Undirected Tgrid plots have two peaks, one is at 1 and another is in between {1, 1.5} while GGN has a sharp peak at 1.5 and followed by a smaller peak between {1, 1.5}. These patterns are usually unique and depend on the network itself. Network motifs have been utilized to analyse the topological structure of these networks. It is found that ER network

[EN] In this paper, some results concerning the PageRank versatility measure for multiplex networks are given. This measure extends to the multiplex setting the well-known classic PageRank. Particularly, we focus on some spectral properties of the Laplacian matrix of the multiplex and on obtaining boundaries for the ranking value of a given node when some personalization vector is added, as in the classic setting.

[EN] In this paper, some results concerning the PageRank versatility measure for multiplex networks are given. This measure extends to the multiplex setting the well-known classic PageRank. Particularly, we focus on some spectral properties of the Laplacian matrix of the multiplex and on obtaining boundaries for the ranking value of a given node when some personalization vector is added, as in the classic setting.

In this thesis, we mainly consider two problems about network data. First, we propose a novel statistic of networks, the normalized clustering coefficient, which is a modified version of the clustering coefficient that is robust to network size, network density and degree heterogeneity under different network generative models. In particular, under the degree corrected block model (DCBM), the "in-out-ratio" could be inferred from the normalized clustering coefficient. Asymptotic properties of the proposed indicator are studied under three popular network generative models. The normalized clustering coefficient can also be used for networks clustering, network sampling as well as dynamic network analysis. Simulations and real data analysis are carried out to demonstrate these applications. Second, we propose a new algorithm, called weighted inverse Laplacian (WIL), for predicting labels in partially labeled networks. It is a traditional topic to do community detection in networks. However, it is less discussed how to get more accurate predictions if some of the community labels are observed. The idea comes from the first hitting time in random walk, and it also has nice explanations both in information propagation and the regularization framework. By combining two different kinds of normalization, WIL is more flexible and has more tolerance of community imbalance and degree heterogeneity. We also propose a partially labeled degree-corrected block model (pDCBM) to describe the generation of partially labeled networks. We show that WIL ensures the misclassification rate goes to 0 as the number of nodes goes to infinity, and that it can handle situations with greater imbalance than traditional Laplacian methods. WIL outperforms other state-of-the-art methods in most of our simulations and real datasets, especially in unbalanced networks and heterogeneous networks.

In this thesis, we mainly consider two problems about network data. First, we propose a novel statistic of networks, the normalized clustering coefficient, which is a modified version of the clustering coefficient that is robust to network size, network density and degree heterogeneity under different network generative models. In particular, under the degree corrected block model (DCBM), the "in-out-ratio" could be inferred from the normalized clustering coefficient. Asymptotic properties of the proposed indicator are studied under three popular network generative models. The normalized clustering coefficient can also be used for networks clustering, network sampling as well as dynamic network analysis. Simulations and real data analysis are carried out to demonstrate these applications. Second, we propose a new algorithm, called weighted inverse Laplacian (WIL), for predicting labels in partially labeled networks. It is a traditional topic to do community detection in networks. However, it is less discussed how to get more accurate predictions if some of the community labels are observed. The idea comes from the first hitting time in random walk, and it also has nice explanations both in information propagation and the regularization framework. By combining two different kinds of normalization, WIL is more flexible and has more tolerance of community imbalance and degree heterogeneity. We also propose a partially labeled degree-corrected block model (pDCBM) to describe the generation of partially labeled networks. We show that WIL ensures the misclassification rate goes to 0 as the number of nodes goes to infinity, and that it can handle situations with greater imbalance than traditional Laplacian methods. WIL outperforms other state-of-the-art methods in most of our simulations and real datasets, especially in unbalanced networks and heterogeneous networks.

Motivation Laplacian matrices capture the global structure of networks and are widely used to study biological networks. However, the local structure of the network around a node can also capture biological information. Local wiring patterns are typically quantified by counting how often a node touches different graphlets (small, connected, induced sub-graphs). Currently available graphlet-based methods do not consider whether nodes are in the same network neighbourhood. To combine graphlet-based topological information and membership of nodes to the same network neighbourhood, we generalize the Laplacian to the Graphlet Laplacian, by considering a pair of nodes to be ‘adjacent’ if they simultaneously touch a given graphlet. Results We utilize Graphlet Laplacians to generalize spectral embedding, spectral clustering and network diffusion. Applying Graphlet Laplacian-based spectral embedding, we visually demonstrate that Graphlet Laplacians capture biological functions. This result is quantified by applying Graphlet Laplacian-based spectral clustering, which uncovers clusters enriched in biological functions dependent on the underlying graphlet. We explain the complementarity of biological functions captured by different Graphlet Laplacians by showing that they capture different local topologies. Finally, diffusing pan-cancer gene mutation scores based on different Graphlet Laplacians, we find complementary sets of cancer-related genes. Hence, we demonstrate that Graphlet Laplacians capture topology-function and topology-disease relationships in biological networks., This work was supported by the European Research Council (ERC) Starting Independent Researcher [Grant 278212]; the European Research Council (ERC) Consolidator [Grant 770827]; the Serbian Ministry of Education and Science [Project III44006]; the Slovenian Research Agency [project J1-8155]; the Prostate Project and UCL Computer Science departmental funds., Peer Reviewed, Postprint (author's final draft)

In this thesis, we mainly consider two problems about network data. First, we propose a novel statistic of networks, the normalized clustering coefficient, which is a modified version of the clustering coefficient that is robust to network size, network density and degree heterogeneity under different network generative models. In particular, under the degree corrected block model (DCBM), the "in-out-ratio" could be inferred from the normalized clustering coefficient. Asymptotic properties of the proposed indicator are studied under three popular network generative models. The normalized clustering coefficient can also be used for networks clustering, network sampling as well as dynamic network analysis. Simulations and real data analysis are carried out to demonstrate these applications. Second, we propose a new algorithm, called weighted inverse Laplacian (WIL), for predicting labels in partially labeled networks. It is a traditional topic to do community detection in networks. However, it is less discussed how to get more accurate predictions if some of the community labels are observed. The idea comes from the first hitting time in random walk, and it also has nice explanations both in information propagation and the regularization framework. By combining two different kinds of normalization, WIL is more flexible and has more tolerance of community imbalance and degree heterogeneity. We also propose a partially labeled degree-corrected block model (pDCBM) to describe the generation of partially labeled networks. We show that WIL ensures the misclassification rate goes to 0 as the number of nodes goes to infinity, and that it can handle situations with greater imbalance than traditional Laplacian methods. WIL outperforms other state-of-the-art methods in most of our simulations and real datasets, especially in unbalanced networks and heterogeneous networks.

In this paper, we give conditions for the existence of periodic behaviors in a multi-agent system of identical discrete-time double integrators with input saturation constraints. If the feedback gain parameters of the controllers, which are based on relative state measurements of the agent itself and its neighboring agents, are bounded by a value depending on the largest eigenvalue of the Laplacian matrix, then the multi-agent system exhibits a periodic solution for certain initial conditions., QC 20140912

A current challenge in evolutionary ecology is to assess how the spatial structure of interacting species shapes coevolution. Previous work on the geographic mosaic of coevolution has shown that coevolution depends on the spatial structure, the strength of selection, and gene flow across populations. We used spatial subgraphs and coevolutionary models to evaluate how spatial structure and the location of coevolutionary hotspots (sites in which reciprocal selection occurs) and coldspots (sites in which unidirectional selection occurs) contribute to the dynamics of coevolution and the maintenance of polymorphisms. Specifically, we developed a new approach based on the Laplacian matrices of spatial subgraphs to explore the tendency of interacting species to evolve toward stable polymorphisms. Despite the complex interplay between gene flow and the strength of reciprocal selection, simple rules drive coevolution in small groups of spatially structured interacting populations. Hotspot location and the spatial organization of coldspots are crucial for understanding patterns in the maintenance of polymorphisms. Moreover, the degree of spatial variation in the outcomes of the coevolutionary process can be predicted from the network pattern of gene flow among sites. Our work provides us with novel tools that can be used in the field or the laboratory to predict the effects of spatial structure on coevolutionary trajectories.

A current challenge in evolutionary ecology is to assess how the spatial structure of interacting species shapes coevolution. Previous work on the geographic mosaic of coevolution has shown that coevolution depends on the spatial structure, the strength of selection, and gene flow across populations. We used spatial subgraphs and coevolutionary models to evaluate how spatial structure and the location of coevolutionary hotspots (sites in which reciprocal selection occurs) and coldspots (sites in which unidirectional selection occurs) contribute to the dynamics of coevolution and the maintenance of polymorphisms. Specifically, we developed a new approach based on the Laplacian matrices of spatial subgraphs to explore the tendency of interacting species to evolve toward stable polymorphisms. Despite the complex interplay between gene flow and the strength of reciprocal selection, simple rules drive coevolution in small groups of spatially structured interacting populations. Hotspot location and the spatial organization of coldspots are crucial for understanding patterns in the maintenance of polymorphisms. Moreover, the degree of spatial variation in the outcomes of the coevolutionary process can be predicted from the network pattern of gene flow among sites. Our work provides us with novel tools that can be used in the field or the laboratory to predict the effects of spatial structure on coevolutionary trajectories.

We study the time scales associated with diffusion processes that take place on multiplex networks, i.e., on a set of networks linked through interconnected layers. To this end, we propose the construction of a supra-Laplacian matrix, which consists of a dimensional lifting of the Laplacian matrix of each layer of the multiplex network. We use perturbative analysis to reveal analytically the structure of eigenvectors and eigenvalues of the complete network in terms of the spectral properties of the individual layers. The spectrum of the supra-Laplacian allows us to understand the physics of diffusionlike processes on top of multiplex networks. © 2013 American Physical Society.

We give a de nition of the fractional Laplacian on some noncompact manifolds, through an extension problem introduced by Ca arelli-Silvestre. While this de nition in the compact case is straightforward, in the noncompact setting one needs to have a precise control of the behavior of the metric at in nity and geometry plays a crucial role. First we give explicit calculations in the hyperbolic space, including a formula for the kernel and a trace Sobolev inequality. Then we consider more general noncompact manifolds, where the problem reduces to obtain suitable upper bounds for the heat kernel., Preprint

Summary: In this work, we develop an extension of the generalized Fourier transform for exterior domains due to T. Ikebe and A. Ramm for all dimensions n>2 to study the Laplacian, and fractional Laplacian operators in such a domain. Using the harmonic extension approach due to L. Caffarelli and L. Silvestre, we can obtain a localized version of the operator, so that it is precisely the square root of the Laplacian as a self-adjoint operator in L2 with DIrichlet boundary conditions. In turn, this allowed us to obtain a maximum principle for solutions of the dissipative two-dimensional quasi-geostrophic equation the exterior domain, which we apply to prove decay results using an adaptation of the Fourier Splitting method of M.E. Schonbek., by Leonardo Kosloff., Thesis (Ph.D.)--Florida Atlantic University, 2012., Includes bibliography., Mode of access: World Wide Web., System requirements: Adobe Reader.

We study the synchronization of a set of SISO subsystems interconnected via a time-invariant Laplacian matrix. By synchronization we mean that the outputs of all subsystems must be asymptotically equal to each other and behave in the same manner. We assume that the subsystems can be represented as the sum of a common nonzero transfer function plus a perturbation. A Nyquist-type criterion is established which ensures synchronization provided that the convex hull of the frequency responses of the subsystems does not intersect a certain region defined by the spectrum of the interconnection matrix. The result is applied to a variety of examples of different nature for which synchronization takes place. A counter example for which complete synchronization is impossible is also presented., QC 20140908