共查询到20条相似文献，搜索用时 0 毫秒
1.
Francesco Caravenna Alessandro Garavaglia Remco van der Hofstad 《Random Structures and Algorithms》2019,54(3):444-498
It is well known that many random graphs with infinite variance degrees are ultra‐small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k?(τ ? 1) with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to and , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order precisely when the minimal forward degree dfwd of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature. 相似文献
2.
Abbas Mehrabian 《Random Structures and Algorithms》2017,50(2):201-224
We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three‐fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank‐based selection model, the Aiello‐Chung‐Lu models, the generalized linear preference model, directed scale‐free graphs, the Cooper‐Frieze model, and random unordered increasing k‐trees. Our results shed light on why the small‐world phenomenon is observed in so many real‐world graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 201–224, 2017 相似文献
3.
WILLIAM J. REED 《Natural Resource Modeling》2006,19(1):3-14
ABSTRACT. This article provides a brief introduction to scale‐free networks. The notion of a scale‐free network is defined and some examples given. Properties frequently exhibited by scale‐free networks are discussed. The importance of the phenomenon of preferential attachment in generating scale‐free networks is illustrated with two examples for the spread of a persistent disease. The models are similar in that they both yield a total infected population (1) which is geometrically distributed, and growing exponentially in expectation; and (2) in which the average distance from the original source of infection grows in a similar way over time. However one model, which has preferential attachment (infection), yields a scale‐free network, while the other which has homogeneous infectivity does not. The possible application of the theory of scale‐free networks to resource management is briefly discussed. 相似文献
4.
5.
In this article, we focus on discussing the degree distribution of the DMS model from the perspective of probability. On the basis of the concept and technique of first-passage probability in Markov theory, we provide a rigorous proof for existence of the steady-state degree distribution, mathematically re-deriving the exact formula of the distribution. The approach based on Markov chain theory is universal and performs well in a large class of growing networks. 相似文献
6.
In this article, we develop a simple model for the effect of gossip spread on social network structure. We define gossip as information passed between two individuals A and B about a third individual C which affects the strengths of all three relationships: it strengthens A‐B and weakens both B‐C and A‐C. We find, in both an analytic derivation and model simulations, that if gossip does not spread beyond simple triads, it destroys them but if gossip propagates through large dense clusters, it strengthens them. Additionally, our simulations show that the effect of gossip on network metrics (clustering coefficient, average‐path‐length, and sum‐of‐strengths) varies with network structure and average‐node‐degree. © 2010 Wiley Periodicals, Inc. Complexity 16: 39‐47, 2011 相似文献
7.
In this article we introduce a new random mapping model, , which maps the set {1,2,…,n} into itself. The random mapping is constructed using a collection of exchangeable random variables which satisfy . In the random digraph, , which represents the mapping , the in‐degree sequence for the vertices is given by the variables , and, in some sense, can be viewed as an analogue of the general independent degree models from random graph theory. We show that the distribution of the number of cyclic points, the number of components, and the size of a typical component can be expressed in terms of expectations of various functions of . We also consider two special examples of which correspond to random mappings with preferential and anti‐preferential attachment, respectively, and determine, for these examples, exact and asymptotic distributions for the statistics mentioned above. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献
8.
Jesus Felix Valenzuela Christopher Monterola Erika Fille Legara Xiuju Fu Rick Siow Mong Goh 《Complexity》2015,21(1):283-295
We examine the transmission of entities from the peripheries of scale‐free networks toward their centers when the nodes of the network have finite processing capabilities. We look at varying network utilization, U and find that clogging of the network sets in after a threshold value has been exceeded, and that the congestion sets in at the downstream nodes (those nearer to the collector) having large numbers of upstream neighbors. Investigation of the question of the degree of correlation of several characteristics of scale‐free networks (such as the average path length to the collector <l(min)> and the average clustering coefficient ) with the dynamics of centripetal flow in them reveals a negative answer: any correlation is indirect and will manifest in the number of producer nodes (which dictate the effective heaviness of the flow) and the interconnectedness of the feeder nodes, those nodes which are immediate neighbors of the collector node. An examination of reinforcement strategies shows dramatic improvements in both the finishing rate, and the average total transmission time, when the more centrally‐placed nodes are reinforced first, showing that the entities spend a large amount of their lifetime waiting in line at those nodes (which constitute the bottlenecks in the network) compared to the nodes in the periphery. Our results reinforce the importance of a network's hubs and their immediate environs, and suggest strategies for prioritizing elements of a network for optimization. © 2014 Wiley Periodicals, Inc. Complexity 21: 283–295, 2015 相似文献
9.
Complex networks with multiple nodes and diverse interactions among them are ubiquitous. We suggest that optimal networks spontaneously emerge when “information” transfer is maximized at the least expense. We support our hypothesis by evolving optimal topologies for a particle swarm optimizer (PSO), a population‐based stochastic algorithm. Results suggest that (1) an optimum topology emerges at the phase transition when connectivity is high enough to transfer information but low enough to prevent premature convergence, and (2) Small World (SW) networks are a compromise between higher performance and resistance to mutation. The graph characteristics of the optimal PSO networks in the SW regime are similar to that of the visual cortices of cat and macaque, thereby suggesting similar design principles. © 2006 Wiley Periodicals, Inc. Complexity 11:26–35, 2006 相似文献
10.
增长网络的形成机理和度分布计算 总被引：1，自引：0，他引：1
关于增长网络的形成机理,着重介绍由线性增长与择优连接组成的BA模型, 以及加速增长模型.此外,我们提出了一个含反择优概率删除旧连线的模型,这个模型能自组织演化成scale-free(SF)网络.关于计算SF网络的度分布,简要介绍文献上常用的基于连续性理论的动力学方法(包括平均场和率方程)和基于概率理论的主方程方法.另外,我们基于马尔可夫链理论还首次尝试了数值计算方法.这一方法避免了复杂方程的求解困难,所以较有普适性,因此可用于研究更为复杂的网络模型.我们用这种数值计算方法研究了一个具有对数增长的加速增长模型,这个模型也能自组织演化成SF网络. 相似文献
11.
David Dfossez 《Journal of Graph Theory》2006,53(3):233-249
We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K4‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006 相似文献
12.
In this paper we propose a simple evolving network with link additions as well as removals. The preferential attachment of link additions is similar to BA model’s, while the removal rule is newly added. From the perspective of Markov chain, we give the exact solution of the degree distribution and show that whether the network is scale-free or not depends on the parameter m, and the degree exponent varying in （3, 5] is also depend on m if scale-free. 相似文献
13.
The structure of interaction plays an important role in the outcome of evolutionary games. This study investigates the evolution of stochastic strategies of the prisoner's dilemma played on structures ranging from lattices to small world networks. Strategies and payoffs are analyzed as a function of the network characteristics of the node they are playing on. Nodes with lattice‐like neighborhoods tend to perform better than the nodes modified during the rewiring process of the construction of the small‐world network. © 2007 Wiley Periodicals, Inc. Complexity 12:22–36, 2006 相似文献
14.
We study three preferential attachment models where the parameters are such that the asymptotic degree distribution has infinite variance. Every edge is equipped with a nonnegative i.i.d. weight. We study the weighted distance between two vertices chosen uniformly at random, the typical weighted distance, and the number of edges on this path, the typical hopcount. We prove that there are precisely two universality classes of weight distributions, called the explosive and conservative class. In the explosive class, we show that the typical weighted distance converges in distribution to the sum of two i.i.d. finite random variables. In the conservative class, we prove that the typical weighted distance tends to infinity, and we give an explicit expression for the main growth term, as well as for the hopcount. Under a mild assumption on the weight distribution the fluctuations around the main term are tight. 相似文献
15.
Given a weighted graph G, in the minimum-cost-edge-selection problem (MCES), a minimum weighted set of edges is chosen subject to an upper bound on the diameter of graph G. Similarly, in the minimum-diameter-edge-selection problem (MDES), a set of edges is chosen to minimize the diameter subject to an upper bound on their total weight. These problems are shown to be equivalent and proven to be NP-complete. MCES is then formulated as a 0–1 integer programming problem. The problems MCES and MDES provide models for determining smallest-world networks and for measuring the “small-worldness” of graphs. 相似文献
16.
基于度与路径优先连接的集聚型供应链网络演化模型 总被引：2，自引：0，他引：2
集聚型供应链供应链网络具有无标度性、高集聚性等特征.以往研究忽视了供应链网络的高集聚性,使得供应链网络模型不能够准确刻画实际的集聚型供应链网络.本文在具体分析集聚型供应链网络动态演化特征的基础上,提出了基于度与路径优先连接的集聚型供应链网络演化模型,弥补了优先连接仅依赖于节点度值的不足.最后,对集聚型供应链网络的度分布、集聚系数和平均最短路径参数进行了数值模拟,模拟结果表明,该模型不仅能够反映集聚型供应链网络的无标度性,而且能够真实刻画其高集聚性特征. 相似文献
17.
Objective: The study aimed to analyze sexual networks and sex role preference as factors of HIV transmission among men who have sex with men (MSM) in China. Methods: We have developed a new scale‐free network model with a sex role preference framework to study HIV transmission among MSM. We have studied the influence of different sexual networks and the effect of different proportion of sex role preference upon HIV transmission. The results are that the average ones drawn from the scenarios have been simulated for more than 30 times. Results: Compared with the traditional mathematical model, the sexual networks provide a different prediction of the HIV transmission in the next 30 years. Without any intervention, the proportion of HIV carriers will descend after some time. Conclusions: There is significant associations among network characteristics, sex role preference, and HIV infection. Although network‐based intervention is efficient in reducing HIV transmission among MSM, there are only few studies of the characteristics of sexual network, and such gaps deserve more attention and exploration. Copyright © 2016 John Wiley & Sons, Ltd. 相似文献
18.
通过分析几种估计增长网络度分布方法的缺点,提出估计度分布的差分方程方法,不仅避免了复杂网络分析中将离散问题连续化带来的逻辑矛盾,也避免了网络稳态度分布存在性的假设．利用这个方法给出Poisson增长择优连接网络的度分布公式,借助Poisson过程理论和Gamma分布的性质严格证明Poisson增长择优连接网络是无标度网络． 相似文献
19.
A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γt(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γt(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γt(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009 相似文献
20.
在一个常规构建的图中加“长边(shortcuts)”会得到一个小世界模型,这是经典的构造小世界模型的方法.最近,吴宪远在文[Internet Mathematics,DOI:10.1080/15427951,2015.101208]中指出,在加“长边”过程中加的所有边,只有与图的直径成正比才会对小世界模型的构造起决定性... 相似文献