×

zbMATH — the first resource for mathematics

Analysis of a model for generating weakly scale-free networks. (English) Zbl 1450.05082
Summary: It is commonly believed that real networks are scale-free and fraction of nodes \(P(k)\) with degree \(k\) satisfies the power law \(P(k) \propto k^{-\gamma} \text{ for } k > k_{\min} > 0\). Preferential attachment is the mechanism that has been considered responsible for such organization of these networks. In many real networks, degree distribution before the \(k_{\min}\) varies very slowly to the extent of being uniform as compared with the degree distribution for \(k > k_{\min}\) . In this paper, we proposed a model that describe this particular degree distribution for the whole range of \(k>0\). We adopt a two step approach. In the first step, at every time stamp we add a new node to the network and attach it with an existing node using preferential attachment method. In the second step, we add edges between existing pairs of nodes with the node selection based on the uniform probability distribution. Our approach generates weakly scale-free networks that closely follow the degree distribution of real-world networks. We perform comprehensive mathematical analysis of the model in the discrete domain and compare the degree distribution generated by these models with that of real-world networks.
MSC:
05C82 Small world graphs, complex networks (graph-theoretic aspects)
90B10 Deterministic network models in operations research
Software:
plfit; KONECT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Y.-Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong. Analysis of topological characteristics of huge online social networking services. InProceedings of the 16th International Conference on World Wide Web, WWW ’07, pages 835-844, 2007.
[2] R. Albert and A.-L. Barab´asi. Topology of evolving networks: Local events and universality.Physical Review Letters, 85:5234-5237, 2000.
[3] L. A. N. Amaral, A. Scala, M. Barth´el´emy, and H. E. Stanley. Classes of small-world networks.Proceedings of the National Academy of Sciences, 97(21):11149-11152, 2000.
[4] A.-L. Barabasi and R. Albert. Emergence of scaling in random networks.Science, 286(5439):509-512, 1999. · Zbl 1226.05223
[5] Generating Weakly Scale-free Networks15
[6] N. Berger, C. Borgs, J. T. Chayes, R. M. D’Souza, and R. D. Kleinberg. Competition-induced preferential attachment. InAutomata, Languages and Programming, pages 208-221, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. · Zbl 1098.68009
[7] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. InProceedings of the 9th International World Wide Web Conference on Computer Networks : The International Journal of Computer and Telecommunications Netowrking, pages 309-320, 2000.
[8] A. D. Broido and A. Clauset. Scale-free Networks are Rare, 2018.
[9] M. Brzezinski. Power laws in citation distributions: evidence from Scopus.Scientometrics, 103(1): 213-228, April 2015.
[10] A. Clauset, C. R. Shalizi, and M. E. J. Newman. Power-law distributions in empirical data.SIAM Review, 51(4):661-703, 2009. · Zbl 1176.62001
[11] A. Collevecchio, C. Cotar, and M. LiCalzi. On a preferential attachment and generalized p ´Olya’s urn model.The Annals of Applied Probability, 23(3):1219-1253, 2013. · Zbl 1266.05150
[12] C. Cooper and A. Frieze. A general model of web graphs.Random Struct. Algorithms, 22(3):311-335, May 2003. ISSN 1042-9832. · Zbl 1018.60007
[13] M. Deijfen, H. van den Esker, R. van der Hofstad, and G. Hooghiemstra. A preferential attachment model with random initial degrees.Arkiv f¨or Matematik, 47(1):41-72, Apr 2009. · Zbl 1182.05107
[14] S. Dorogovtsev and J. F. Mendes. Language as an evolving word web.Proceedings. Biological sciences / The Royal Society, 268:2603-6, 01 2002a.
[15] S. Dorogovtsev and J. F. Mendes. Evolution of networks.Advances In Physics, 51:1079-1187, 06 2002b.
[16] S. Dorogovtsev, J. F. Mendes, and A. N Samukhin. Structure of growing networks with preferential linking.Physical review letters, 85:4633-6, 11 2000.
[17] S. N. Dorogovtsev and J. F. F. Mendes. Scaling behaviour of developing and decaying networks.Europhysics Letters (EPL), 52(1):33-39, oct 2000.
[18] S. N. Dorogovtsev and J. F. F. Mendes. Accelerated growth of networks.CoRR, cond-mat/0204102, 2002c.
[19] S. A. Golder, D. M. Wilkinson, and B. A. Huberman.Rhythms of Social Interaction: Messaging Within a Massive Online Network, pages 41-66. Springer London, London, 2007.
[20] S. H. Strogatz. Exploring complex networks.Nature, International Journal of Science, 410, 03 2001. · Zbl 1370.90052
[21] KONECT.The Koblenz Network Collection - KONECT, Apr. 2017.URLhttp://konect. uni-koblenz.de/networks/.
[22] P. L. Krapivsky, S. Redner, and F. Leyvraz. Connectivity of growing random networks.Phys. Rev. Lett., 85:4629-4632, Nov 2000.
[23] 16Raheel Anwar, Muhammad Irfan Yousuf, Muhammad Abid
[24] R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. InProceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’06, pages 611-617, 2006.
[25] P. Lansky, F. Polito, and L. Sacerdote. The role of detachment of in-links in scale-free networks.Journal of Physics A: Mathematical and Theoretical, 47(34), aug 2014. · Zbl 1296.90129
[26] P. Lansky, F. Polito, and L. Sacerdote. Generalized nonlinear yule models.Journal of Statistical Physics, 165(3):661-679, Nov 2016. · Zbl 1362.60039
[27] A. Magner, S. Janson, G. Kollias, and W. Szpankowski. On symmetry of uniform and preferential attachment graphs.The Electronic Journal of Combinatorics [electronic only], 21, 08 2014. · Zbl 1331.05197
[28] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and analysis of online social networks. InProceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, IMC ’07, pages 29-42, 2007.
[29] M. E. J. Newman.The structure of scientific collaboration networks.Proceedings of the National Academy of Sciences, 98(2):404-409, 2001. · Zbl 1065.00518
[30] I. Ortu˜no, J. A. Crespo, P. Albarr´an, and J. Ruiz-Castillo. The skewness of science in 219 sub-fields and a number of aggregates. UC3M Working papers. Economics we1109, Universidad Carlos III de Madrid. Departamento de Econom´ıa, May 2011. URLhttps://ideas.repec.org/p/cte/werepe/ we1109.html.
[31] L. Ostroumova, A. Ryabchenko, and E. Samosvat. Generalized preferential attachment: Tunable powerlaw degree distribution and clustering coefficient. InAlgorithms and Models for the Web Graph, pages 185-202, Cham, 2013. Springer International Publishing. · Zbl 1347.68020
[32] A. Pach´on, F. Polito, and L. Sacerdote. Random graphs associated to some discrete and continuous time preferential attachment models.Journal of Statistical Physics, 162:1608-1638, 03 2016. doi: 10.1007/s10955-016-1462-7. · Zbl 1336.05118
[33] A. Pach´on, L. Sacerdote, and S. Yang. Scale-free behavior of networks with the copresence of preferential and uniform attachment rules.Physica D: Nonlinear Phenomena, 04 2017. doi: 10.1016/j.physd.2018. 01.005.
[34] A. Rudas, B. T´oth, and B. Valk´o. Random trees and general branching processes.Random Structures & Algorithms, 31(2):186-202, 2007. · Zbl 1144.60051
[35] A. Vazquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of the internet.Physical review. E, Statistical, nonlinear, and soft matter physics, 65, 07 2002.
[36] AGeneral form of Recurrence Relation for degree distribution
[37] A general form of the recurrence relation for degree distribution will be derived here. Recurrence formula
[38] writesPk,t+1, rank of nodes of degreekat timet+ 1, in terms ofPh,tforh=k, k−1, . . .. Network
[39] Generating Weakly Scale-free Networks17
[40] evolution is based on both the node- and edge- steps. The formulation is valid whether∆mtis constant
[41] for all time steps or varies by the rule (given in B). The relation fork= 1. Using Equation (13) repeatedly forl= 1,2, . . . ,∆mt, we get
[42] We will write general form of the recurrence relation fork >1. LetΦ =t+12andΨ = 1−t+12. Then rewriting the recurrence relation (12), for forl= 1and generall, in the following form:
[43] 18Raheel Anwar, Muhammad Irfan Yousuf, Muhammad Abid
[44] Last term in square brackets occurs only whenq= ∆mt< k−1. During the application of the limit,
[45] limt→ ∞, this situation can occur only when∆mtis a fixed number. In the other case, where∆mt
[46] varies,∆mt→ ∞, this term does not appear in the recurrence relation. Simplifying further,we get q
[47] (t+ 1)Pk,t+1= 1−Ck,∆mtPk,t+1−Ck−n,∆m+Ck−n+1,∆mtPk−n,t 2mtt2mtt2mtt
[48] forn= 0, we get k0
[49] Key observations:Before deriving exact form of these coefficients, we list few key points about these
[50] coefficients. 00
[51] Generating Weakly Scale-free Networks19 0
[52] ofl=nedges. Forl < n, Ck−n,l= 0. Putting in the mathematical form, forn= 1,2...andn < k, 0
[53] Ck,∆mt 0
[54] Finally, k−12∆mt−12k−12∆mt
[55] 20Raheel Anwar, Muhammad Irfan Yousuf, Muhammad Abid 00
[56] Finally we get, k−20k−20
[57] Ck−n,∆mare the same. Order ofCk−n,∆mtisO(∆mtn)× O(1) =O((∆mt)n). ttnt
[58] A.1∆mt=α
[59] This section derives recurrence relation for ranksPk’s when number of edges is a fixed constantαfor
[60] each time stept.
[61] k= 1 Consider eqn. (A.1) for∆mt=α
[62] Generating Weakly Scale-free Networks21 or
[63] recurrence relation eqn. (A.2). Ck,α
[64] tPk,twill be cancelled out by the term on L.H.S.(A.2).tCk,αPk,tapproaches to−k+ 2αP 2(α+1)k.
[65] 22Raheel Anwar, Muhammad Irfan Yousuf, Muhammad Abid
[66] Maximum order term in thetCk−2,αis of orderO(1t).The termtCk−2,αvanishes to0on taking limit
[67] limt→∞. Ck−n,αfork > nforn= 3,4, ...
[68] tCk−n,αis of ordertn1−1.tCk−n,αforn= 3,4, ...vanishes on applying the limit. Now we have all limitslimt→∞tCk−n,αrequired to determine limiting value of the equation (A.2).
[69] Equation (A.2) on applying limit becomes k−1k
[70] BVariable∆mt
[71] Here, for the sake of completion, we will discuss the case when∆mtvaries with timetand find recurrence
[72] relation. It varies at each time stept, with∆mt+ 1is proportional to the fraction of the total number of
[73] edges by the number of nodes. Recurrence relation will be derived only formally.
[74] B.1The number of edges in edge-step at time stept
[75] The number of edges at the completion of time stept(both node and edge-step completed ) ismt.∆mt
[76] is the number of edges to be added during the edge-step. As mentioned earlier, this number is determined
[77] by the fraction of edges by number of nodes.∆mt=dβmtte −1, with parameterβas a real number
[78] greater than1. For the current analysis,β∈(1,2). After the node-step, total number of number of edges
[79] aremt+1.mt+1, the total number of edges after the completion of both node- and edge- steps, is given
[80] by the relation mt+1=mt+ ∆mt+ 1,
[81] We selectβsuch thatβmtt>>1,∆mt≈βmtt.
[82] It implies that, β
[83] Generating Weakly Scale-free Networks23
[84] which gives good approximation for the factorials of large number, can be used here to get simplified form
[85] of the above expression. Using this approximation, expression formt+1reduces to 1(β+t)β+t+12
[86] B.2Recurrence relation for degree distribution
[87] k= 1 Consider the equation A.1 once again.
[88] Let us write equation into the form where we can cancel the highest order terms. 2∆mtk2∆mtk
[89] R.H.S. becomes1. Let us now evaluate L.H.S. limit. 2∆mtk
[90] is the reduced form of the L.H.S. limit.
[91] 24Raheel Anwar, Muhammad Irfan Yousuf, Muhammad Abid Equating both limits,
[92] 0,1, . . . Ck,∆mt
[93] tCk,∆mt), with 2∆mtk
[94] of ordertβ−1. Thus the coefficient of is ofPk,thas orderO(∆mt). Ck−1,∆mt This coefficient exists fork >1.
[95] Generating Weakly Scale-free Networks25 ConsidertCk−1,∆mt,
[96] contains2∆mtas a maximum order term. Thus2∆mtis maximum order coefficient ofPk−1,t. In short,
[97] O(tβ−1)is the order oftCk−1,∆mtPk−1,t. Ck−2,∆mtfork >2 This coefficient exists fork >2.
[98] Thus maximum order coefficient ofPk−2,thas the orderO(t2β−3). This term when divided by the term
[99] of the orderO(tβ−1), results into a term of ordertβ−2, which will approach to0forβ <2. Ck−n,∆mtfork > nforn= 3,4, ...
[100] Ck−n,∆mt=ak∆−mnΨ∆mt−nΦnwithak−nis ofO(∆mn t∆mtt).
[101] the equation bytβ−1, we get coefficients ofPk−n,tof ordert(n−1)(β−2)that vanishes to0forβ <2on
[102] applying the limitlimt→∞. Thus, on applyinglimt→∞to (A.2), following expression is obtained: lim1 + 2∆mt+. . .Pk= lim[2∆mt]Pk−1.
[103] or Pk=P1.
[104] a stationary degree distribution. Then the above relationship shows thatlimt→∞Pk,t→Pkand results
[105] intoPk≡0∀k, which contradicts the constraint. It means that we do not get a stationary distribution
[106] and it is a time dependent satisfying the constraintPKk=1tPk,t= 1, withKtas the maximum degree of
[107] the network node, growing at each time step. The network is no longer a scale-free network but converts
[108] to a network with uniform degree distribution. We can estimate the value ofKt. For larget, and for all
[109] k >1,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.