k-core is a notion capturing the cohesiveness of a subgraph in a social network graph. Most of the current research work only consider pure network graphs and neglect an important property of the nodes: influence. Li, Qin, Yu, and Mao introduced a novel community model called k-influential community which is based on the concept of k-core enhanced with node influence values. In this model, we are interested not only in subgraphs that are well-connected but also have a high lower-bound on their influence. More precisely, we are interested in finding top r (with respect to influence), k-core communities. We present novel approaches that provide an impressive scalability in solving the problem for graphs of billions of edges using only a consumer-grade machine. / Graduate

Since the late 1980s there has been a greater awareness of the need to manage organisational knowledge resources, which are seen as vital to the value proposition of any organisation. This has resulted in the development of a multiplicity of Organisational Knowledge Management (OKM) approaches, systems and processes. OKM as a concept is however experiencing a prolonged period of practitioner and academic dissatisfaction, which is impacting its credibility. Commentators claim that this emanates from the fact that a general model, as a diagnostic mechanism for the field, has not yet emerged, an indicator of immaturity in the field and a destabilising influence on practitioner confidence. This research sets out to explore OKM, with the aim of understanding and attempting to help address this dissatisfaction. The literature review focuses on environmental drivers of OKM as a concept from both practitioner and academic perspectives. This highlights a need for (1) an agreed definition of purpose for OKM systems and (2) a general diagnostic model or framework for those systems that identifies common constructs across sectors or geographic locations. In turn, these require appropriate research evidence. The research reported on in this thesis utilises Soft Systems Methodology as a framework for enquiry. By means of a meta-analysis of literature, the enquiry progresses to a descriptive survey, with findings being illustrated and analysed through fractal analysis. The data is then compared against a sample of models from the field before being translated into a new OKM diagnostic model and supporting toolkit, using logic modelling and a Participatory Integrated Assessment Tool. The application of these to a case study, carried out within in a large multinational organisation, is reported on and evaluated. Findings are that 'self-similarity' exists across existing views of OKM; that the need for knowledge to be used as an organisational resource is a persistent one; that a methodology can be developed that reacts to the needs of academics and practitioners in responding to the challenges from the field; that a proposition for a general organisation diagnostic model is possible; that a robust evidence-based definition for the concept, as well as a general diagnostic model for the coordination of organisational knowledge resources is needed and are provided; and that such a general diagnostic tool, such as has been developed in the research on which this thesis is based, can be applied within an organisation to identify gaps in systems designed to coordinate organisational knowledge resources.

<p>Research interests in the studies of complex systems have been booming in many disciplines for the last decade. As the nature of geographic environment is a complex system, researches in this field are anticipated. In particular, the urban street networks in the Geographic Information System (GIS) as complex networks are brought forth for the thesis study. Meanwhile, identifying the scale-free property, which is represented as the power law distribution from a mathematical perspective, is a hot topic in the studies of complex systems. Many previous studies estimated the power law distributions with graphic method, which used linear regression method to identify the exponent value and estimate the quality that the power law fits to the empirical data. However, such strategy is considered to cause inaccurate results and lead to biased judgments. Whereas, the Maximum Likelihood Estimation (MLE) and the Goodness of fit test based on Kolmogorov-Smironv (KS) statistics will provide more solid and trustable results for the estimations. Therefore, this thesis addresses these updated methods exploring the topological patterns of urban street networks from an analytical perspective, which is estimating the power law distributions for the connectivity degree and length of the urban streets. Simultaneously, this thesis explores the street networks from a visual perspective as well. The visual perspective adopts the large network visualization tool (LaNet-vi), which is developed based on the k-core decomposition algorithm, to analyze the cores of the urban street networks. By retrieving the spatial information of the networks from GIS, it actually enables us to see how the urban street networks decomposed topologically and spatially. In particular, the 40 US urban street networks are reformed as natural street networks by using three "natural street" models.</p><p>The results from analytical perspective show that the 80/20 principle still exists for both the street connectivity degree and length qualitatively, which means around 20% natural streets in each network have a connectivity degree or length value above the average level, while the 80% ones are below the average. Moreover, the quantitative analysis revealed the fact that most of the distributions from the street connectivity degree or length of the 40 natural street networks follow a power law distribution with an exponential cut-off. Some of the rest cases are verified to have power law distributions and some extreme cases are still unclear for identifying which distribution form to fit. The comparisons are made to the power law statement from previous study which used the linear regression method. Moreover, the visual perspective not only provides us the chance to see the inner structures about the hierarchies and cores of the natural street networks topologically and spatially, but also serves as a reflection for the analytical perspective. Such relationships are discussed and the possibility of combining these two aspects are pointed out. In addition, the future work is also proposed for making better studies in this field.</p>

Research interests in the studies of complex systems have been booming in many disciplines for the last decade. As the nature of geographic environment is a complex system, researches in this field are anticipated. In particular, the urban street networks in the Geographic Information System (GIS) as complex networks are brought forth for the thesis study. Meanwhile, identifying the scale-free property, which is represented as the power law distribution from a mathematical perspective, is a hot topic in the studies of complex systems. Many previous studies estimated the power law distributions with graphic method, which used linear regression method to identify the exponent value and estimate the quality that the power law fits to the empirical data. However, such strategy is considered to cause inaccurate results and lead to biased judgments. Whereas, the Maximum Likelihood Estimation (MLE) and the Goodness of fit test based on Kolmogorov-Smironv (KS) statistics will provide more solid and trustable results for the estimations. Therefore, this thesis addresses these updated methods exploring the topological patterns of urban street networks from an analytical perspective, which is estimating the power law distributions for the connectivity degree and length of the urban streets. Simultaneously, this thesis explores the street networks from a visual perspective as well. The visual perspective adopts the large network visualization tool (LaNet-vi), which is developed based on the k-core decomposition algorithm, to analyze the cores of the urban street networks. By retrieving the spatial information of the networks from GIS, it actually enables us to see how the urban street networks decomposed topologically and spatially. In particular, the 40 US urban street networks are reformed as natural street networks by using three "natural street" models. The results from analytical perspective show that the 80/20 principle still exists for both the street connectivity degree and length qualitatively, which means around 20% natural streets in each network have a connectivity degree or length value above the average level, while the 80% ones are below the average. Moreover, the quantitative analysis revealed the fact that most of the distributions from the street connectivity degree or length of the 40 natural street networks follow a power law distribution with an exponential cut-off. Some of the rest cases are verified to have power law distributions and some extreme cases are still unclear for identifying which distribution form to fit. The comparisons are made to the power law statement from previous study which used the linear regression method. Moreover, the visual perspective not only provides us the chance to see the inner structures about the hierarchies and cores of the natural street networks topologically and spatially, but also serves as a reflection for the analytical perspective. Such relationships are discussed and the possibility of combining these two aspects are pointed out. In addition, the future work is also proposed for making better studies in this field.

Systems such as the power grid, world wide web (WWW), and internet are categorized as complex systems because of the presence of a large number of interacting elements. For example, the WWW is estimated to have a billion webpages and understanding the dynamics of such a large number of individual agents (whose individual interactions might not be fully known) is a challenging task. Complex network representations of these systems have proved to be of great utility. Statistical physics is the study of emergence of macroscopic properties of systems from the characteristics of the interactions between individual molecules. Hence, statistical physics of complex networks has been an effective approach to study these systems. In this dissertation, I have used statistical physics to study two distinct phenomena in complex systems: i) Cascading failures and ii) Shortest paths in complex networks. Understanding cascading failures is considered to be one of the “holy grails“ in the study of complex systems such as the power grid, transportation networks, and economic systems. Studying failures of these systems as percolation on complex networks has proved to be insightful. Previously, cascading failures have been studied extensively using two different models: k-core percolation and interdependent networks. The first part of this work combines the two models into a general model, solves it analytically, and validates the theoretical predictions through extensive computer simulations. The phase diagram of the percolation transition has been systematically studied as one varies the average local k-core threshold and the coupling between networks. The phase diagram of the combined processes is very rich and includes novel features that do not appear in the models which study each of the processes separately. For example, the phase diagram consists of first- and second-order transition regions separated by two tricritical lines that merge together and enclose a two-stage transition region. In the two-stage transition, the size of the giant component undergoes a first-order jump at a certain occupation probability followed by a continuous second-order transition at a smaller occupation probability. Furthermore, at certain fixed interdependencies, the percolation transition cycles from first-order to second-order to two-stage to first-order as the k-core threshold is increased. We setup the analytical equations describing the phase boundaries of the two-stage transition region and we derive the critical exponents for each type of transition. Understanding the shortest paths between individual elements in systems like communication networks and social media networks is important in the study of information cascades in these systems. Often, large heterogeneity can be present in the connections between nodes in these networks. Certain sets of nodes can be more highly connected among themselves than with the nodes from other sets. These sets of nodes are often referred to as ’communities’. The second part of this work studies the effect of the presence of communities on the distribution of shortest paths in a network using a modular Erdős-Rényi network model. In this model, the number of communities and the degree of modularity of the network can be tuned using the parameters of the model. We find that the model reaches a percolation threshold while tuning the degree of modularity of the network and the distribution of the shortest paths in the network can be used as an indicator of how the communities are connected.

No description available.

No description available.

This thesis is comprised of three parts. The first part describes a novel framework for computing importance measures on graph vertices. The concept of a D-spectrum is introduced, based on vertex ranks within certain chains of nested sub-graphs. We show that the D- spectrum integrates the degree distribution and coreness information of the graph as two particular such chains. We prove that these spectra are realized as fixed points of certain monotone and contractive SDSs we call t-systems. Finally, we give a vertex deletion algorithm that efficiently computes D-spectra, and we illustrate their correlation with stochastic SIR-processes on real world networks. The second part deals with the topology of the intersection nerve for a bi-secondary structure, and its singular homology. A bi-secondary structure R, is a combinatorial object that can be viewed as a collection of cycles (loops) of certain at most tetravalent planar graphs. Bi-secondary structures arise naturally in the study of RNA riboswitches - molecules that have an MFE binary structural degeneracy. We prove that this loop nerve complex has a euclidean 3-space embedding characterized solely by H2(R), its second homology group. We show that this group is the only non-trivial one in the sequence and furthermore it is free abelian. The third part further describes the features of the loop nerve. We identify certain disjoint objects in the structure of R which we call crossing components (CC). These are non-trivial connected components of a graph that captures a particular non-planar embedding of R. We show that each CC contributes a unique generator to H2(R) and thus the total number of these crossing components in fact equals the rank of the second homology group. / Doctor of Philosophy / This Thesis is divided into three parts. The first part describes a novel mathematical framework for decomposing a real world network into layers. A network is comprised of interconnected nodes and can model anything from transportation of goods to the way the internet is organized. Two key numbers describe the local and global features of a network: the number of neighbors, and the number of neighbors in a certain layer, a node has. Our work shows that there are other numbers in-between the two, that better characterize a node. We also give explicit means of computing them. Finally, we show that these numbers are connected to the way information spreads on the network, uncovering a relation between the network’s structure and dynamics on said network. The last two parts of the thesis have a common theme and study the same mathematical object. In the first part of the two, we provide a new model for the way riboswtiches organize themselves. Riboswitches, are RNA molecules within a cell, that can take two mutually opposite conformations, depending on what function they need to perform within said cell. They are important from an evolutionary standpoint and are actively studied within that context, usually being modeled as networks. Our model captures the shapes of the two possible conformations, and encodes it within a mathematical object called a topological space. Once this is done, we prove that certain numbers that are attached to all topological spaces carry specific values for riboswitches. Namely, we show that the shapes of the two possible conformations for a riboswich are always characterized by a single integer. In the last part of the Thesis we identify what exactly in the structure of riboswitches contributes to this number being large or small. We prove that the more tangled the two conformations are, the larger the number. We can thus conclude that this number is directly proportional to how complex the riboswitch is.

No description available.