In this article, the popularly discussed topic, i.e., how to construct available theoretical networked models that certainly capture some structural features popularly observed on realistic networks, is still our focus. Specifically, we first propose an evolving deterministic network \(N(t)\) using three types of growth ways. Then, we study some topological structural parameters including degree distribution, diameter, and clustering coefficient on network \(N(t)\) . The results demonstrate that the proposed network has scale-free feature and small-world property. In the meantime, we obtain an interesting finding, i.e., the first handshake between Fibonacci series and the “pure” preferential attachment mechanism. Next, we enumerate spanning trees on network \(N(t)\) and derive the closed-form solution of spanning trees number. Second, we introduce randomness into the growth process of network \(N(t)\) to further establish evolving stochastic networks \(\mathfrak{N}(t)\) that follow the same degree distribution as network \(N(t)\) and also determine some topological structural parameters so as to investigate effect of randomness on structural properties. We show analytically that such a randomization approach makes the resulting stochastic networks not only to greatly inherit some fundamental structural properties from deterministic network \(N(t)\) but also to considerably improve the robustness of network when encountering deliberate removal of edge. Lastly, we list out some open problems.

Scale-free networks are prevalently observed in a great variety of complex systems, which triggers various researches relevant to networked models of such type. In this work, we propose a family of growth tree networks \(\mathcal{T}_{t}\) , which turn out to be scale-free, in an iterative manner. As opposed to most of published tree models with scale-free feature, our tree networks have the power-law exponent \(\gamma=1{ + }\ln 5/\ln 2\) that is obviously larger than \(3\) . At the same time, “small-world” property can not be found particularly because models \(\mathcal{T}_{t}\) have an ultra-large diameter \(D_{t}\) (i.e., \(D_{t}\sim|\mathcal{T}_{t}|^{\ln 3/\ln 5}\) ) and a greater average shortest path length \(\langle\mathcal{W}_{t}\rangle\) (namely, \(\langle\mathcal{W}_{t}\rangle\sim|\mathcal{T}_{t}|^{\ln 3/\ln 5}\) ) where \(|\mathcal{T}_{t}|\) represents vertex number. Next, we determine Pearson correlation coefficient and verify that networks \(\mathcal{T}_{t}\) display disassortative mixing structure. In addition, we study random walks on tree networks \(\mathcal{T}_{t}\) and derive exact solution to mean hitting time \(\langle\mathcal{H}_{t}\rangle\) . The results suggest that the analytic formula for quantity \(\langle\mathcal{H}_{t}\rangle\) as a function of vertex number \(|\mathcal{T}_{t}|\) shows a power-law form, i.e., \(\langle\mathcal{H}_{t}\rangle\sim|\mathcal{T}_{t}|^{1+\ln 3/\ln 5}\) . Accordingly, we execute extensive experimental simulations, and demonstrate that empirical analysis is in strong agreement with theoretical results. Lastly, we provide a guide to extend the proposed iterative manner in order to generate more general scale-free tree networks with large diameter.

As known, the commonly-utilized ways to determine mean first-passage time F for random walk on networks are mainly based on Laplacian spectra. However, methods of this type can become prohibitively complicated and even fail to work when the Laplacian matrix of network under consideration is difficult to describe in the first place. In this paper, we propose an effective approach to determining quantity F on some widely-studied tree networks. To this end, we first build up a general formula between Wiener index W and F on a tree. This enables us to convert issues to answer into calculation of W on networks in question. As opposed to most of previous work focusing on deterministic growth trees, our goal is to consider stochastic case. Towards this end, we establish a principled framework where randomness is introduced into the process of growing trees. As an immediate consequence, the previously published results upon deterministic cases are thoroughly covered by formulas established in this paper. Additionally, it is also straightforward to obtain Kirchhoff index on our tree networks using the proposed approach. Most importantly, our approach is more manageable than some other methods including spectral technique in situations considered herein

Local differential privacy (LDP for short), as an emerging standard privacy-preserving technique that is suitable for privacy preserving data analysis, has been widely deployed into various real-world scenarios to analyze massive data. In this study, we are mainly concerned with piecewise transformation technique (PTT for short) for analyzing numerical data under LDP. We first provide the principled framework for PTT in the context of LDP. Then, we show that (1) many PTTs are asymptotically optimal when used to obtain an unbiased estimator for mean of numerical data, and (2) there is PTT that reaches the theoretical lower bound on variance. Next, we prove that (1) there does not exist strictly better PTT than the well-used Duchi's scheme in terms of the consistency-noisy-variance, also, the latter is not always better than arbitrary PTT, (2) however, one has the ability to find a great number of PTTs that are consistently better than the latter according to the worst-case-noisy-variance. When we are restricted to the high privacy level$\epsilon \in (0,1]$, enough PTTs turn out to have smaller variance than the well-known Laplace mechanism. Lastly, we demonstrate that for a family of PTTs, the correspondingly theoretical lower bound of noisy variance follows$O(\epsilon ^{-2})$when considering$\epsilon \in (0,1]$.

In this work, we propose a principled framework using Vertex-based and Edge-based uniform generation mechanisms to build stochastic uniform growth tree networks that have a wide range of applications in various fields including physics, engineering, chemistry, ect., and then uncover the associated structural features analytically. When considering vertex-degree distribution, there exist three different classes of forms in the thermodynamic limit, i.e., exponential distribution, power-law distribution along with multiple-point distribution. At meantime, three distinct structural shapes are observed in the study of fractal phenomena, that is, fractal feature, critical phenomenon and non-fractal property. In addition, we obtain the analytical solution to fractal dimension for fractal structure from the probability point of view. More importantly, some well-known models, for instance, Vicsek fractal and T-graph, fall into our framework. Next, we precisely consider two families of stochastic uniform growth tree networks generated through the proposed framework. Specifically, we derive the analytic solution to mean hitting time$\langle \mathcal {H}\rangle$for measuring efficiency of delivering information on networks in a random-walk-based manner, and find that the introduction of randomness certainly enriches the scaling exponent of quantity$\langle \mathcal {H}\rangle$. Finally, we conduct extensive experiments, which suggests that computer simulations are in good agreement with theoretical analysis.

Geodesic distance, sometimes called shortest path length, has proven useful in a great variety of applications, such as information retrieval on networks including treelike networked models. Here, our goal is to analytically determine the exact solutions to geodesic distances on two different families of growth trees which are recursively created upon an arbitrary tree$\mathcal {T}$using two types of well-known operations, first-order subdivision and ($1,m$)-star-fractal operation. Different from commonly-used methods, for instance, spectral techniques, for addressing such a problem on growth trees using a single edge as seed in the literature, we propose a novel method for deriving closed-form solutions on the presented trees completely. Meanwhile, our technique is more general and convenient to implement compared to those previous methods mainly because there are not complicated calculations needed. In addition, the closed-form expression of mean first-passage time ($MFPT$) for random walk on each member in tree families is also readily obtained according to connection of our obtained results to effective resistance of corresponding electric networks. The results suggest that the two topological operations above are sharply different from each other due to$MFPT$for random walks, and, however, have likely to show the similar performance, at least, on geodesic distance.

Abstract The problem of determining closed-form solutions for some structural parameters of great interest on networked models is meaningful and intriguing. In this paper, we propose a family of networked models $\mathcal{G}_{n}(t)$ with hierarchical structure where $t$ represents time step and $n$ is copy number. And then, we study some structural parameters on the proposed models $\mathcal{G}_{n}(t)$ in more detail. The results show that (i) models $\mathcal{G}_{n}(t)$ follow power-law distribution with exponent $2$ and thus exhibit density feature; (ii) models $\mathcal{G}_{n}(t)$ have both higher clustering coefficients and an ultra-small diameter and so display small-world property; and (iii) models $\mathcal{G}_{n}(t)$ possess rich mixing structure because Pearson-correlated coefficients undergo phase transitions unseen in previously published networked models. In addition, we also consider trapping problem on networked models $\mathcal{G}_{n}(t)$ and then precisely derive a solution for average trapping time $ATT$. More importantly, the analytic value for $ATT$ can be approximately equal to the theoretical lower bound in the large graph size limit, implying that models $\mathcal{G}_{n}(t)$ are capable of having most optimal trapping efficiency. As a result, we also derive exact solution for another significant parameter, Kemeny’s constant. Furthermore, we conduct extensive simulations that are in perfect agreement with all the theoretical deductions.