اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTriangle Preferential Attachment Has Power-law Degrees and Eigenvalues; Eigenvalues Are More Stable to Network Sampling
394
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Preferential attachment models are a common class of graph models which have been used to explain why power-law distributions appear in the degree sequences of real network data. One of the things they lack, however, is higher-order network clustering, including non-trivial clustering coefficients. In this paper we present a specific Triangle Generalized Preferential Attachment Model (TGPA) that, by construction, has nontrivial clustering. We further prove that this model has a power-law in both the degree distribution and eigenvalue spectra. We use this model to investigate a recent finding that power-laws are more reliably observed in the eigenvalue spectra of real-world networks than in their degree distribution. One conjectured explanation for this is that the spectra of the graph is more robust to various sampling strategies that would have been employed to collect the real-world data compared with the degree distribution. Consequently, we generate random TGPA models that provably have a power-law in both, and sample subgraphs via forest fire, depth-first, and random edge models. We find that the samples show a power-law in the spectra even when only 30% of the network is seen. Whereas there is a large chance that the degrees will not show a power-law. Our TGPA model shows this behavior much more clearly than a standard preferential attachment model. This provides one possible explanation for why power-laws may be seen frequently in the spectra of real world data.
قيم البحث
اقرأ أيضاً
Preferential attachment (PA) models of network structure are widely used due to their explanatory power and conceptual simplicity. PA models are able to account for the scale-free degree distributions observed in many real-world large networks throug
h the remarkably simple mechanism of sequentially introducing nodes that attach preferentially to high-degree nodes. The ability to efficiently generate instances from PA models is a key asset in understanding both the models themselves and the real networks that they represent. Surprisingly, little attention has been paid to the problem of efficient instance generation. In this paper, we show that the complexity of generating network instances from a PA model depends on the preference function of the model, provide efficient data structures that work under any preference function, and present empirical results from an implementation based on these data structures. We demonstrate that, by indexing growing networks with a simple augmented heap, we can implement a network generator which scales many orders of magnitude beyond existing capabilities ($10^6$ -- $10^8$ nodes). We show the utility of an efficient and general PA network generator by investigating the consequences of varying the preference functions of an existing model. We also provide quicknet, a freely-available open-source implementation of the methods described in this work.
In this paper, a random graph process ${G(t)}_{tgeq 1}$ is studied and its degree sequence is analyzed. Let $(W_t)_{tgeq 1}$ be an i.i.d. sequence. The graph process is defined so that, at each integer time $t$, a new vertex, with $W_t$ edges attache
d to it, is added to the graph. The new edges added at time t are then preferentially connected to older vertices, i.e., conditionally on $G(t-1)$, the probability that a given edge is connected to vertex i is proportional to $d_i(t-1)+delta$, where $d_i(t-1)$ is the degree of vertex $i$ at time $t-1$, independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent $tau=min{tau_{W}, tau_{P}}$, where $tau_{W}$ is the power-law exponent of the initial degrees $(W_t)_{tgeq 1}$ and $tau_{P}$ the exponent predicted by pure preferential attachment. This result extends previous work by Cooper and Frieze, which is surveyed.
Despite the moduli space of triangles being three dimensional, we prove the existence of two triangles which are not isometric to each other for which the first, second and fourth Dirichlet eigenvalues coincide, establishing a numerical observation f
rom Antunes-Freitas [P. R. S. Antunes and P. Freitas. Proc. R. Soc. Lond.Ser. A Math. Phys. Eng. Sci., 467(2130):1546-1562, 2011]. The two triangles are far from any known, explicit cases. To do so, we develop new tools to rigorously enclose eigenvalues to a very high precision, as well as their position in the spectrum. This result is also mentioned as (the negative part of) Conjecture 6.46 in [R. Laugesen, B. Siudeja, Shape optimization and spectral theory, 149-200. De Gruyter Open, Warsaw, 2017], Open Problem 1 in [D. Grieser, S. Maronna, Notices Amer. Math. Soc., 60(11):1440-1447, 2013] and Conjecture 3 in [Z. Lu, J. Rowlett. Amer. Math. Monthly, 122(9):815-835, 2015.].
We present a simple model of network growth and solve it by writing down the dynamic equations for its macroscopic characteristics like the degree distribution and degree correlations. This allows us to study carefully the percolation transition usin
g a generating functions theory. The model considers a network with a fixed number of nodes wherein links are introduced using degree-dependent linking probabilities $p_k$. To illustrate the techniques and support our findings using Monte-Carlo simulations, we introduce the exemplary linking rule $p_k$ proportional to $k^{-alpha}$, with $alpha$ between -1 and plus infinity. This parameter may be used to interpolate between different regimes. For negative $alpha$, links are most likely attached to high-degree nodes. On the other hand, in case $alpha>0$, nodes with low degrees are connected and the model asymptotically approaches a process undergoing explosive percolation.
Let $G$ be a graph. For a subset $X$ of $V(G)$, the switching $sigma$ of $G$ is the signed graph $G^{sigma}$ obtained from $G$ by reversing the signs of all edges between $X$ and $V(G)setminus X$. Let $A(G^{sigma})$ be the adjacency matrix of $G^{sig
ma}$. An eigenvalue of $A(G^{sigma})$ is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Let $S_{n,k}$ be the graph obtained from the complete graph $K_{n-r}$ by attaching $r$ pendent edges at some vertex of $K_{n-r}$. In this paper we prove that there exists a switching $sigma$ such that all eigenvalues of $G^{sigma}$ are main when $G$ is a complete multipartite graph, or $G$ is a harmonic tree, or $G$ is $S_{n,k}$. These results partly confirm a conjecture of Akbari et al.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
