An ensemble of random graphs with identical degree distribution

Comparative analysis of Ball Mapper and conventional Mapper in investigating air pollutants' behavior

This study investigates the effectiveness and efficiency of two topological data analysis (TDA) techniques, the conventional Mapper (CM) and its variant version, the Ball Mapper (BM), in analyzing the behavior of six major air pollutants (NO2, PM10, PM2.5, O3, CO, and SO2) across 60 air quality monitoring stations in Malaysia. Topological graphs produced by CM and BM reveal redundant monitoring stations and geographical relationships corresponding to air pollutant behavior, providing better visualization than traditional hierarchical clustering. Additionally, a comparative analysis of topological graph structures was conducted using node degree distribution, topological graph indices, and Dynamic Time Warping (DTW) to evaluate the sensitivity and performance of these TDA techniques. Both approaches yielded valuable insights in representing the air quality monitoring stations network; however, the complexity of CM, which requires multiple parameters, poses a challenge in graph construction. In contrast, the simplicity of BM, requiring only a single parameter, is preferable for representing air pollutant behavior. The findings suggest an alternative approach for assessing and identifying redundancies in air quality monitoring stations, which could contribute to improved air quality monitoring management and more effective regulatory policies.

Stochastic growth tree networks with an identical fractal dimension: Construction and mean hitting time for random walks

There is little attention paid to stochastic tree networks in comparison with the corresponding deterministic analogs in the current study of fractal trees. In this paper, we propose a principled framework for producing a family of stochastic growth tree networks _T possessing fractal characteristic, where t represents the time step and parameter m is the number of vertices newly created for each existing vertex at generation. To this end, we introduce two types of generative ways, i.e., Edge-Operation and Edge-Vertex-Operation. More interestingly, the resulting stochastic trees turn out to have an identical fractal dimension _d = ln ⁡ 2 ( m + 1 ) / ln ⁡ 2 regardless of the introduction of randomness in the growth process. At the same time, we also study many other structural parameters including diameter and degree distribution. In both extreme cases, our tree networks are deterministic and follow multiple-point degree distribution and power-law degree distribution, respectively. Additionally, we consider random walks on stochastic growth tree networks _T and derive an expectation estimation for mean hitting time ⟨ _H ⟩ in an effective combinatorial manner instead of commonly used spectral methods. The result shows that on average, the scaling of mean hitting time ⟨ _H ⟩ obeys ⟨ _H ⟩ = | _T ^|, where | _T | represents vertex number and exponent λ is equivalent to 1 + ln ⁡ 2 / ln ⁡ 2 ( m + 1 ). In the meantime, we conduct extensive experimental simulations and observe that empirical analysis is in strong agreement with theoretical results.

A general model of hierarchical fractal scale-free networks

We propose a general model of unweighted and undirected networks having the scale-free property and fractal nature. Unlike the existing models of fractal scale-free networks (FSFNs), the present model can systematically and widely change the network structure. In this model, an FSFN is iteratively formed by replacing each edge in the previous generation network with a small graph called a generator. The choice of generators enables us to control the scale-free property, fractality, and other structural properties of hierarchical FSFNs. We calculate theoretically various characteristic quantities of networks, such as the exponent of the power-law degree distribution, fractal dimension, average clustering coefficient, global clustering coefficient, and joint probability describing the nearest-neighbor degree correlation. As an example of analyses of phenomena occurring on FSFNs, we also present the critical point and critical exponents of the bond-percolation transition on infinite FSFNs, which is related to the robustness of networks against edge removal. By comparing the percolation critical points of FSFNs whose structural properties are the same as each other except for the clustering nature, we clarify the effect of the clustering on the robustness of FSFNs. As demonstrated by this example, the present model makes it possible to elucidate how a specific structural property influences a phenomenon occurring on FSFNs by varying systematically the structures of FSFNs. Finally, we extend our model for deterministic FSFNs to a model of non-deterministic ones by introducing asymmetric generators and reexamine all characteristic quantities and the percolation problem for such non-deterministic FSFNs.

Random growth scale-free networked models with an identical degree distribution and a tunable assortativity index

In this work, we propose two kinds of graphic operations by using triangle configuration, based on which we establish a family of random growth networked models G(t;p) where notations t and p represent time step and probability parameter, respectively. By studying some fundamental structural parameters both analytically and numerically, we show that (1) all the realizations G(t;p) follow the same power-law degree distribution with exponent γ=2+ln⁡3/ln⁡2 regardless of probability p and thus have scale-free feature; (2) each model G(t;p) has a relatively high clustering coefficient; and (3) while network G(t;1) has a small average path length, it is not a unique model possessing small-world property mainly because its diameter D(t;1) does not reach the theoretical lower bound. Next, we make use of assortativity index R to quantify the tendency of forming connection between vertices and observe that (1) model G(t;0) exhibits disassortative mixing because the corresponding index R(t;0) is non-positive, and (2) model G(t;1) is in the opposite direction. As a result, we demonstrate that random model G(t;p) has a tunable quantity R(t;p) controlled by probability p. In addition, we exactly determine the total number of spanning trees of deterministic models G(t;1) and G(t;0) and also calculate the entropy of spanning trees.

Random growth networks with exponential degree distribution

A great variety of complex networks can be well represented as random graphs with some constraints: for instance, a provided degree distribution, a smaller diameter, and a higher clustering coefficient. Among them, the degree distribution has attracted considerable attention from various science communities in the last few decades. In this paper, we focus mainly on a family of random graphs modeling complex networks that have an exponential degree distribution; i.e., P(k)∼ exp(αk), where k is the degree of a vertex, P(k) is a probability for choosing randomly a vertex with degree equal to k, and α is a constant. To do so, we first introduce two types of operations: type-A operation and type-B operation. By both the helpful operations, we propose an available algorithm A for a seminal model to construct exactly solvable random graphs, which are able to be extended to a graph space S(p,p^c,t) with probability parameters p and p^c satisfying p+p^c=1. Based on the graph space S(p,p^c,t), we discuss several topological structure properties of interest on each member N(p,p^c,t) itself and find model N(p,p^c,t) to exhibit the small-world property and assortative mixing. In addition, we also report a fact that in some cases, two arbitrarily chosen members might have completely different other topological properties, such as the total number of spanning trees, although they share a degree distribution in common. Extensive experimental simulations are in strong agreement with our analytical results.

Dense networks with scale-free feature

While previous works have shown that an overwhelming number of scale-free networks are sparse, there still exist some real-world networks including social networks, urban networks, information networks, which are by observation dense. In this paper, we propose a framework for generating scale-free graphs with a dense feature using two simple yet helpful operations: first-order subdivision and line operation. From the theoretical point of view, our method can be used not only to produce desired scale-free graphs with a density feature, i.e., a power-law exponent γ falling into the interval 1<γ≤2, but also to establish many other unexpected networked models, for instance, power-law models having a large diameter. In addition, the networked models generated upon our framework show an especially assortative structure. That is, their own Pearson correlation coefficients are able to achieve the theoretical upper bound. Last but not the least, we find the sizes of community in the proposed models to follow the power law in a form with respect to modularity maximization.

Constructions and properties of a class of random scale-free networks

Complex networks have abundant and extensive applications in real life. Recently, researchers have proposed a large variety of complex networks, in which some are deterministic and others are random. The goal of this paper is to generate a class of random scale-free networks. To achieve this, we introduce three types of operations, i.e., rectangle operation, diamond operation, and triangle operation, and provide the concrete process for generating random scale-free networks N(p,q,r,t), where probability parameters p,q,r hold on p+q+r=1 with 0≤p,q,r≤1. We then discuss their topological properties, such as average degree, degree distribution, diameter, and clustering coefficient. First, we calculate the average degree of each member and discover that each member is a sparse graph. Second, by computing the degree distribution of our network N(p,q,r,t), we find that degree distribution obeys the power-law distribution, which implies that each member is scale-free. Next, according to our analysis of the diameter of our network N(p,q,r,t), we reveal the fact that the diameter may abruptly transform from small to large. Afterward, we give the calculation process of the clustering coefficient and discover that its value is mainly determined by r.