Multifractal characterisation and analysis of complex networks

Complex networks have been studied extensively due to their relevance to many real-world systems such as the world-wide web, the internet, biological and social systems. During the past two decades, studies of such networks in different fields have produced many significant results concerning their structures, topological properties, and dynamics. Three well-known properties of complex networks are scale-free degree distribution, small-world effect and self-similarity. The search for additional meaningful properties and the relationships among these properties is an active area of current research. This thesis investigates a newer aspect of complex networks, namely their multifractality, which is an extension of the concept of selfsimilarity. The first part of the thesis aims to confirm that the study of properties of complex networks can be expanded to a wider field including more complex weighted networks. Those real networks that have been shown to possess the self-similarity property in the existing literature are all unweighted networks. We use the proteinprotein interaction (PPI) networks as a key example to show that their weighted networks inherit the self-similarity from the original unweighted networks. Firstly, we confirm that the random sequential box-covering algorithm is an effective tool to compute the fractal dimension of complex networks. This is demonstrated on the Homo sapiens and E. coli PPI networks as well as their skeletons. Our results verify that the fractal dimension of the skeleton is smaller than that of the original network due to the shortest distance between nodes is larger in the skeleton, hence for a fixed box-size more boxes will be needed to cover the skeleton. Then we adopt the iterative scoring method to generate weighted PPI networks of five species, namely Homo sapiens, E. coli, yeast, C. elegans and Arabidopsis Thaliana. By using the random sequential box-covering algorithm, we calculate the fractal dimensions for both the original unweighted PPI networks and the generated weighted networks. The results show that self-similarity is still present in generated weighted PPI networks. This implication will be useful for our treatment of the networks in the third part of the thesis. The second part of the thesis aims to explore the multifractal behavior of different complex networks. Fractals such as the Cantor set, the Koch curve and the Sierspinski gasket are homogeneous since these fractals consist of a geometrical figure which repeats on an ever-reduced scale. Fractal analysis is a useful method for their study. However, real-world fractals are not homogeneous; there is rarely an identical motif repeated on all scales. Their singularity may vary on different subsets; implying that these objects are multifractal. Multifractal analysis is a useful way to systematically characterize the spatial heterogeneity of both theoretical and experimental fractal patterns. However, the tools for multifractal analysis of objects in Euclidean space are not suitable for complex networks. In this thesis, we propose a new box covering algorithm for multifractal analysis of complex networks. This algorithm is demonstrated in the computation of the generalized fractal dimensions of some theoretical networks, namely scale-free networks, small-world networks, random networks, and a kind of real networks, namely PPI networks of different species. Our main finding is the existence of multifractality in scale-free networks and PPI networks, while the multifractal behaviour is not confirmed for small-world networks and random networks. As another application, we generate gene interactions networks for patients and healthy people using the correlation coefficients between microarrays of different genes. Our results confirm the existence of multifractality in gene interactions networks. This multifractal analysis then provides a potentially useful tool for gene clustering and identification. The third part of the thesis aims to investigate the topological properties of networks constructed from time series. Characterizing complicated dynamics from time series is a fundamental problem of continuing interest in a wide variety of fields. Recent works indicate that complex network theory can be a powerful tool to analyse time series. Many existing methods for transforming time series into complex networks share a common feature: they define the connectivity of a complex network by the mutual proximity of different parts (e.g., individual states, state vectors, or cycles) of a single trajectory. In this thesis, we propose a new method to construct networks of time series: we define nodes by vectors of a certain length in the time series, and weight of edges between any two nodes by the Euclidean distance between the corresponding two vectors. We apply this method to build networks for fractional Brownian motions, whose long-range dependence is characterised by their Hurst exponent. We verify the validity of this method by showing that time series with stronger correlation, hence larger Hurst exponent, tend to have smaller fractal dimension, hence smoother sample paths. We then construct networks via the technique of horizontal visibility graph (HVG), which has been widely used recently. We confirm a known linear relationship between the Hurst exponent of fractional Brownian motion and the fractal dimension of the corresponding HVG network. In the first application, we apply our newly developed box-covering algorithm to calculate the generalized fractal dimensions of the HVG networks of fractional Brownian motions as well as those for binomial cascades and five bacterial genomes. The results confirm the monoscaling of fractional Brownian motion and the multifractality of the rest. As an additional application, we discuss the resilience of networks constructed from time series via two different approaches: visibility graph and horizontal visibility graph. Our finding is that the degree distribution of VG networks of fractional Brownian motions is scale-free (i.e., having a power law) meaning that one needs to destroy a large percentage of nodes before the network collapses into isolated parts; while for HVG networks of fractional Brownian motions, the degree distribution has exponential tails, implying that HVG networks would not survive the same kind of attack.

A linear programming approach for estimating the structure of a sparse linear genetic network from transcript profiling data

Background: A genetic network can be represented as a directed graph in which a node corresponds to a gene and a directed edge specifies the direction of influence of one gene on another. The reconstruction of such networks from transcript profiling data remains an important yet challenging endeavor. A transcript profile specifies the abundances of many genes in a biological sample of interest. Prevailing strategies for learning the structure of a genetic network from high-dimensional transcript profiling data assume sparsity and linearity. Many methods consider relatively small directed graphs, inferring graphs with up to a few hundred nodes. This work examines large undirected graphs representations of genetic networks, graphs with many thousands of nodes where an undirected edge between two nodes does not indicate the direction of influence, and the problem of estimating the structure of such a sparse linear genetic network (SLGN) from transcript profiling data. Results: The structure learning task is cast as a sparse linear regression problem which is then posed as a LASSO (l1-constrained fitting) problem and solved finally by formulating a Linear Program (LP). A bound on the Generalization Error of this approach is given in terms of the Leave-One-Out Error. The accuracy and utility of LP-SLGNs is assessed quantitatively and qualitatively using simulated and real data. The Dialogue for Reverse Engineering Assessments and Methods (DREAM) initiative provides gold standard data sets and evaluation metrics that enable and facilitate the comparison of algorithms for deducing the structure of networks. The structures of LP-SLGNs estimated from the INSILICO1, INSILICO2 and INSILICO3 simulated DREAM2 data sets are comparable to those proposed by the first and/or second ranked teams in the DREAM2 competition. The structures of LP-SLGNs estimated from two published Saccharomyces cerevisae cell cycle transcript profiling data sets capture known regulatory associations. In each S. cerevisiae LP-SLGN, the number of nodes with a particular degree follows an approximate power law suggesting that its degree distributions is similar to that observed in real-world networks. Inspection of these LP-SLGNs suggests biological hypotheses amenable to experimental verification. Conclusion: A statistically robust and computationally efficient LP-based method for estimating the topology of a large sparse undirected graph from high-dimensional data yields representations of genetic networks that are biologically plausible and useful abstractions of the structures of real genetic networks. Analysis of the statistical and topological properties of learned LP-SLGNs may have practical value; for example, genes with high random walk betweenness, a measure of the centrality of a node in a graph, are good candidates for intervention studies and hence integrated computational – experimental investigations designed to infer more realistic and sophisticated probabilistic directed graphical model representations of genetic networks. The LP-based solutions of the sparse linear regression problem described here may provide a method for learning the structure of transcription factor networks from transcript profiling and transcription factor binding motif data.

Experimental and Theoretical Charge Density Analysis of Polymorphic Structures: The Case of Coumarin 314 Dye

Experimental charge density distributions in two known conformational polymorphs (orange and yellow) of coumarin 314 dye are analyzed based on multipole modeling of X-ray diffraction data collected at 100 K. The experimental results are compared with the charge densities derived from multipole modeling of theoretical structure factors obtained from periodic quantum calculation with density functional theory (DFT) method and B3LYP/6-31G(d,p) level of theory. The presence of disorder at the carbonyl oxygen atom of ethoxycarbonyl group in the yellow form, which was not identified earlier, is addressed here. The investigationof intermolecular interactions, based on Hirshfeld surface analysis and topological properties via quantum theory of atoms in molecule and total electrostatic interaction energies, revealed significant differences between the polymorphs. The differences of electrostatic nature in these two polymorphic forms were unveiled via construction of three-dimensional deformation electrostatic potential maps plotted over the molecular surfaces. The lattice energies evaluated from ab initio calculations on the two polymorphic forms indicate that the yellow form is likely to be the most favorable thermodynamically. The dipole moments derived from experimental and theoretical charge densities and also from Lorentz tensor approach are compared with the single-molecule dipole moments. In each case, the differences of dipole moments between the polymorphs are identified.

Evolving Random Geometric Graph Models for Mobile Wireless Networks

We consider evolving exponential RGGs in one dimension and characterize the time dependent behavior of some of their topological properties. We consider two evolution models and study one of them detail while providing a summary of the results for the other. In the first model, the inter-nodal gaps evolve according to an exponential AR(1) process that makes the stationary distribution of the node locations exponential. For this model we obtain the one-step conditional connectivity probabilities and extend it to the k-step case. Finite and asymptotic analysis are given. We then obtain the k-step connectivity probability conditioned on the network being disconnected. We also derive the pmf of the first passage time for a connected network to become disconnected. We then describe a random birth-death model where at each instant, the node locations evolve according to an AR(1) process. In addition, a random node is allowed to die while giving birth to a node at another location. We derive properties similar to those above.

Charge density distribution and electrostatic interactions of ethionamide: an inhibitor of the enoyl acyl carrier protein reductase (inhA) enzyme of Mycobacterium tuberculosis

An experimental charge density analysis of an anti-TB drug ethionamide was carried out from high resolution X-ray diffraction at 100 K to understand its charge density distribution and electrostatic properties. The experimental results were validated from periodic theoretical charge density calculations performed using CRYSTAL09 at the B3LYP/6-31G** level of theory. The electron density rho(bcp)(r) and the Laplacian of electron density del(2)(rho bcp)(r) of the molecule calculated from both the methods display the charge density distribution of the ethionamide molecule in the crystal field. The electrostatic potential map shows a large electropositive region around the pyridine ring and a large electronegative region at the vicinity of the thiol atom. The calculated experimental dipole moment is 10.6D, which is higher than the value calculated from theory (8.2D). The topological properties of C-H center dot center dot center dot S, N-H center dot center dot center dot N and N-H center dot center dot center dot S hydrogen bonds were calculated, revealing their strength. The charge density analysis of the ethionamide molecule determined from both the experiment and theory gives the topological and electrostatic properties of the molecule, which allows to precisely understand the nature of intra and intermolecular interactions.

An approximation to the QoS aware throughput region of a tree network under IEEE 802.15.4 CSMA/CA with application to wireless sensor network design

In the context of wireless sensor networks, we are motivated by the design of a tree network spanning a set of source nodes that generate packets, a set of additional relay nodes that only forward packets from the sources, and a data sink. We assume that the paths from the sources to the sink have bounded hop count, that the nodes use the IEEE 802.15.4 CSMA/CA for medium access control, and that there are no hidden terminals. In this setting, starting with a set of simple fixed point equations, we derive explicit conditions on the packet generation rates at the sources, so that the tree network approximately provides certain quality of service (QoS) such as end-to-end delivery probability and mean delay. The structures of our conditions provide insight on the dependence of the network performance on the arrival rate vector, and the topological properties of the tree network. Our numerical experiments suggest that our approximations are able to capture a significant part of the QoS aware throughput region (of a tree network), that is adequate for many sensor network applications. Furthermore, for the special case of equal arrival rates, default backoff parameters, and for a range of values of target QoS, we show that among all path-length-bounded trees (spanning a given set of sources and the data sink) that meet the conditions derived in the paper, a shortest path tree achieves the maximum throughput. (C) 2015 Elsevier B.V. All rights reserved.

Communities in complex networks

The study of complex networks has attracted the attention of the scientific community for many obvious reasons. A vast number of systems, from the brain to ecosystems, power grid, and the Internet, can be represented as large complex networks, i.e, assemblies of many interacting components with nontrivial topological properties. The link between these components can describe a global behaviour such as the Internet traffic, electricity supply service, market trend, etc. One of the most relevant topological feature of graphs representing these complex systems is community structure which aims to identify the modules and, possibly, their hierarchical organization, by only using the information encoded in the graph topology. Deciphering network community structure is not only important in order to characterize the graph topologically, but gives some information both on the formation of the network and on its functionality.

Analysis of Spanish text-thesaurus as a complex network

[EN]Based on the theoretical tools of Complex Networks, this work provides a basic descriptive study of a synonyms dictionary, the Spanish Open Thesaurus represented as a graph. We study the main structural measures of the network compared with those of a random graph. Numerical results show that Open-Thesaurus is a graph whose topological properties approximate a scale-free network, but seems not to present the small-world property because of its sparse structure. We also found that the words of highest betweenness centrality are terms that suggest the vocabulary of psychoanalysis: placer (pleasure), ayudante (in the sense of assistant or worker), and regular (to regulate).

Paranormal operator on a Hilbert space

In this thesis an extensive study is made of the set P of all paranormal operators in B(H), the set of all bounded endomorphisms on the complex Hilbert space H. T ϵ B(H) is paranormal if for each z contained in the resolvent set of T, d(z, σ(T))//(T-zI)^-1 = 1 where d(z, σ(T)) is the distance from z to σ(T), the spectrum of T. P contains the set N of normal operators and P contains the set of hyponormal operators. However, P is contained in L, the set of all T ϵ B(H) such that the convex hull of the spectrum of T is equal to the closure of the numerical range of T. Thus, N≤P≤L.

If the uniform operator (norm) topology is placed on B(H), then the relative topological properties of N, P, L can be discussed. In Section IV, it is shown that: 1) N P and L are arc-wise connected and closed, 2) N, P, and L are nowhere dense subsets of B(H) when dim H ≥ 2, 3) N = P when dimH ˂ ∞ , 4) N is a nowhere dense subset of P when dimH ˂ ∞ , 5) P is not a nowhere dense subset of L when dimH ˂ ∞ , and 6) it is not known if P is a nowhere dense subset of L when dimH ˂ ∞.

The spectral properties of paranormal operators are of current interest in the literature. Putnam [22, 23] has shown that certain points on the boundary of the spectrum of a paranormal operator are either normal eigenvalues or normal approximate eigenvalues. Stampfli [26] has shown that a hyponormal operator with countable spectrum is normal. However, in Theorem 3.3, it is shown that a paranormal operator T with countable spectrum can be written as the direct sum, N ⊕ A, of a normal operator N with σ(N) = σ(T) and of an operator A with σ(A) a subset of the derived set of σ(T). It is then shown that A need not be normal. If we restrict the countable spectrum of T ϵ P to lie on a C²-smooth rectifiable Jordan curve G_o, then T must be normal [see Theorem 3.5 and its Corollary]. If T is a scalar paranormal operator with countable spectrum, then in order to conclude that T is normal the condition of σ(T) ≤ G_o can be relaxed [see Theorem 3.6]. In Theorem 3.7 it is then shown that the above result is not true when T is not assumed to be scalar. It was then conjectured that if T ϵ P with σ(T) ≤ G_o, then T is normal. The proof of Theorem 3.5 relies heavily on the assumption that T has countable spectrum and cannot be generalized. However, the corollary to Theorem 3.9 states that if T ϵ P with σ(T) ≤ G_o, then T has a non-trivial lattice of invariant subspaces. After the completion of most of the work on this thesis, Stampfli [30, 31] published a proof that a paranormal operator T with σ(T) ≤ G_o is normal. His proof uses some rather deep results concerning numerical ranges whereas the proof of Theorem 3.5 uses relatively elementary methods.

Complex networks constructed from irrational number sequences

In this paper, we construct (d, r) networks from sequences of different irrational numbers. In detail, segment an irrational number sequence of length M into groups of d digits which represent the nodes while two consecutive groups overlap by r digits (r = 0,1,...,d-1), and the undirected edges indicate the adjacency between two consecutive groups. (3, r) and (4, r) networks are respectively constructed from 14 different irrational numbers and their topological properties are examined. By observation, we find that network topologies change with different values of d, r and even sequence length M instead of the types of irrational numbers, although they share some similar features with traditional random graphs. We make a further investigation to explain these interesting phenomena and propose the identical-degree random graph model. The results presented in this paper provide some insight into distributions of irrational number digits that may help better understanding of the nature of irrational numbers.

Knotlike chi disclinations in the cholesteric liquid crystals

We investigate the topological properties of N(N >= 1) disclination lines in cholesteric liquid crystals. The topological structure of N disclination lines is obtained with the Hopf index and Brouwer degree. Furthermore, the knotted x disclination loops is proposed with the Hopf invariant. And we consider the stability of such configuration based on the higher order interaction. At last, the evolution of the disclinations is discussed.

Generating Representative ISP Technologies From First-Principles

Understanding and modeling the factors that underlie the growth and evolution of network topologies are basic questions that impact capacity planning, forecasting, and protocol research. Early topology generation work focused on generating network-wide connectivity maps, either at the AS-level or the router-level, typically with an eye towards reproducing abstract properties of observed topologies. But recently, advocates of an alternative "first-principles" approach question the feasibility of realizing representative topologies with simple generative models that do not explicitly incorporate real-world constraints, such as the relative costs of router configurations, into the model. Our work synthesizes these two lines by designing a topology generation mechanism that incorporates first-principles constraints. Our goal is more modest than that of constructing an Internet-wide topology: we aim to generate representative topologies for single ISPs. However, our methods also go well beyond previous work, as we annotate these topologies with representative capacity and latency information. Taking only demand for network services over a given region as input, we propose a natural cost model for building and interconnecting PoPs and formulate the resulting optimization problem faced by an ISP. We devise hill-climbing heuristics for this problem and demonstrate that the solutions we obtain are quantitatively similar to those in measured router-level ISP topologies, with respect to both topological properties and fault-tolerance.

Smart design of scaffolds obtained by biofabrication for tissue engineering applications

A engenharia de tecidos é um domínio tecnológico emergente em rápido desenvolvimento que se destina a produzir substitutos viáveis para a restauração, manutenção ou melhoria da função dos tecidos ou órgãos humanos. Uma das estratégias mais predominantes em engenharia de tecidos envolve crescimento celular sobre matrizes de suporte (scaffolds), biocompatíveis e biodegradáveis. Estas matrizes devem possuir não só elevadas propriedades mecânicas e vasculares, mas também uma elevada porosidade. Devido à incompatibilidade destes dois parâmetros, é necessário desenvolver estratégias de simulação de forma a obter estruturas optimizadas. A previsão real das propriedades mecânicas, vasculares e topológicas das matrizes de suporte, produzidas por técnicas de biofabricação, é muito importante para as diversas aplicações em engenharia de tecidos. A presente dissertação apresenta o estado da arte da engenharia de tecidos, bem como as técnicas de biofabricação envolvidas na produção de matrizes de suporte. Para o design optimizado de matrizes de suporte foi adoptada uma metodologia de design baseada tanto em métodos de elementos finitos para o cálculo do comportamento mecânico, vascular e as optimizações topológicas, como em métodos analíticos para a validação das simulações estruturais utilizando dados experimentais. Considerando que as matrizes de suporte são estruturas elementares do tipo LEGO, dois tipos de famílias foram consideradas, superfícies não periódicas e as superfícies triplas periódicas que descrevem superfícies naturais. Os objectivos principais desta dissertação são: i) avaliar as técnicas existentes de engenharia de tecidos; ii) avaliar as técnicas existentes de biofabricação para a produção de matrizes de suporte; iii) avaliar o desempenho e comportamento das matrizes de suporte; iv) implementar uma metodologia de design de matrizes de suporte em variáveis tais como a porosidade, geometria e comportamento mecânico e vascular por forma a auxiliar o processo de design; e por fim, v) validar experimentalmente a metodologia adoptada.

Surfaces de Riemann compactes et formule de trace d'Eichler

Dans ce mémoire, nous étudierons quelques propriétés algébriques, géométriques et topologiques des surfaces de Riemann compactes. Deux grand sujets seront traités. Tout d'abord, en utilisant le fait que toute surface de Riemann compacte de genre g plus grand ou égal à 2 possède un nombre fini de points de Weierstrass, nous allons pouvoir conclure que ces surfaces possèdent un nombre fini d'automorphismes. Ensuite, nous allons étudier de plus près la formule de trace d'Eichler. Ce théorème nous permet de trouver le caractère d'un automorphisme agissant sur l'espace des q-différentielles holomorphes. Nous commencerons notre étude en utilisant la quartique de Klein. Nous effectuerons un exemple de calcul utilisant le théorème d'Eichler, ce qui nous permettra de nous familiariser avec l'énoncé du théorème. Finalement, nous allons démontrer la formule de trace d'Eichler, en prenant soin de traiter le cas où l'automorphisme agit sans point fixe séparément du cas où l'automorphisme possède des points fixes.

Fuzzy Absolutes and Related Topics

The study on the fuzzy absolutes and related topics. The different kinds of extensions especially compactification formed a major area of study in topology. Perfect continuous mappings always preserve certain topological properties. The concept of Fuzzy sets introduced by the American Cyberneticist L. A Zadeh started a revolution in every branch of knowledge and in particular in every branch of mathematics. Fuzziness is a kind of uncertainty and uncertainty of a symbol lies in the lack of well-defined boundaries of the set of objects to which this symbol belongs. Introduce an s-continuous mapping from a topological space to a fuzzy topological space and prove that the image of an H-closed space under an s-continuous mapping is f-H closed. Here also proved that the arbitrary product fi and sum of  fi of the s-continuous maps fi are also s-continuous. The original motivation behind the study of absolutes was the problem of characterizing the projective objects in the category of compact spaces and continuous functions.