1、Evolutionary Models and Dynamical Properties of Complex Networks,Name: Jianguo Liu University of Shanghai for Science and Technology 2010-3-24,Outline,Complex networks analysis by Citespace Network evolution models Dynamical properties on scale-free networks Personalized recommendation,1999年-2010年發(fā)表

2、的以“complex networks”為主題詞的SCI論文數(shù),Citespace軟件介紹,CiteSpace：由美國(guó)德雷賽爾大學(xué)信息科學(xué)與技術(shù)學(xué)院的陳超美開(kāi)發(fā)。該程序可以登錄到/cchen/citespace后免費(fèi)使用。 利用Citespace尋找某一 學(xué)科領(lǐng)域的研究進(jìn)展和當(dāng) 前的研究前沿，及其對(duì)應(yīng) 的基礎(chǔ)知識(shí)。,復(fù)雜網(wǎng)絡(luò)論文作者合作網(wǎng)(1999-2010),復(fù)雜網(wǎng)絡(luò)研究小組狀況(1999-2010),復(fù)雜網(wǎng)絡(luò)各個(gè)國(guó)家研究狀況(1999-2010),利用引文分析觀察當(dāng)前的研究熱點(diǎn)(1999-2010),Top cited authors(1999-

3、2010),各研究領(lǐng)域之間的關(guān)系(1999-2010),個(gè)性化推薦的知識(shí)圖譜,Top cited authors,目前的研究熱點(diǎn),Outline,Background introduction Network evolution models Dynamical properties on scale-free networks Personalized recommendation,2.Scale-free Network Evolution Models,Multistage random growing small-world networks with power-law degree

4、 distribution Growing scale-free network model with tunable assortative coefficient Self-learning mutual selection model for weighted networks Random evolving networks under the diameter and dverage connectivity constraint,2.1.Multistage random growing small-World networks with power-law degree dist

5、ribution,Liu Jian-Guo, Dang Yan-Zhong and Wang Zhong-Tuo, Chinese Physics Letters 23(3) 746-749 (2006),One node is added in each time step； Select the node u according to the preferential mechanism； Select a neighbor node of node u；,One node is added in each time step； Select the node u according to

6、 the preferential mechanism； Select a neighbor node of node u according to ps；,2.2. Growing scale-free network model with tunable assortative coefficient,Qiang Guo, Tao Zhou, Jian-Guo Liu et al., Physica A 371 814-822 (2006),Two parameters: attractive factor p, the number of candidates m,2.3 Self-le

7、arning mutual selection model for weighted networks,Jian-Guo Liu et al., DCDIS B Supplement, Complex Networks, 14 (S7) 33-36, (2007).,1,2,3,4,1,2,3,4,5,m=2,2.4 Random Evolving Networks Under the Diameter and Average Connectivity Constraint,The growth of random networks under the constraint that the

8、diameter, defined as the average shortest path length between all nodes, and the average connectivity remains approximately constant is studied. We showed that, if the network maintains the form of its degree distribution and the maximal degree is a N-dependent cutoff function, then the degree distr

9、ibution would be approximately power-law with an exponent between 2 and 3.,Jian-Guo Liu et al., Journal of System Science and System Engineering 16(1) 107-112 (2007).,Motivation,In the biological networks, the constant diameter may be related to important properties of these biological networks, suc

10、h as the spread and speed of responses to perturbations. In the Internet backbone network, the average distance is one of the most important factors to measure the efficiency of communication network, and it plays a significant role in measuring the transmission delay. These constraints can be thoug

11、ht of as the environmental pressures, which would select highly efficient structure to convey the packets in it.,Motivation,Construction of the model,The expression for the diameter d of a random network with arbitrary degree distribution was developed Where is the average degree,In order to seek a

12、degree distribution that maintains its distribution and has an approximately constant diameter independent of N. The parameter N can be accomplished by imposing a N-dependent cutoff function,The distribution p(k) can be determined by writing this equation for and Algebraic manipulation yields the re

13、lation,Using an integral approximation , a more explicit formulation can be written as following.,When the numerically calculated degree distributions for various values of,Discussion of part two,We have presented a reason for the existence of power-law degree distribution under the diameter constra

14、int observed in the Internet backbone network where there are evolutionary pressures to maintain its diameter. Our analysis shows that, if the maximal degree is a N-dependent cutoff function, the form of a robust network degree distribution should be power law to maintain its diameter, while the ave

15、rage connectivity per node affect the distribution exponent slightly.,Outline,Background introduction Network evolution models Dynamical properties on complex networks Personalized recommendation,3.1 Structural effects on synchronizability of scale-free networks,3.1 How to measure the synchronizabil

16、ity,Where Q is the ratio of the eigenvalues. The synchronizability would be increased as Q decreases, vice verse.,The edge exchange method is introduced to adjust the network structure, and the tabu search algorithm is used to minimize the eigenvalue ratio Q,min,Qiang Guo, Liu Jian-Guo, et al, Chine

17、se Physics Letters 24 (8) (2007) 2437-2440.,In summary, using the tabu optimal algorithm, we have optimized network synchronizability by changing the connection pattern between different pairs of nodes while keeping the degree distribution. Starting from scale-free networks, we have studied the depe

18、ndence between the structural characteristics and synchronizability. The numerical results suggest that a scale-free network with shorter path length, lower degree of clustering, and disassortive pattern can be easily synchronized.,3.1 Structural effects on synchronizability,min,max,Combining the ta

19、bu search (TS) algorithm and the edge exchange method, we enhance and weaken the synchronizability of scale-free networks with degree sequence fixed to find the structural effects of the scale-free network on synchronizability,Liu Jian-Guo, et al, International Journal of Modern Physics C 18(7) 1087

20、-1094 (2008).,The numerical results indicate that D, C, r and Bm influence synchronizability simultaneously. Especially, the synchronizability is most sensitive to Bm.,Effect of the loop structure on synchronizability,Outline,Background introduction Network evolution models Dynamical properties on c

21、omplex networks Personalized recommendation,Personalized recommendation,Improved collaborative filtering algorithm based on information transaction. Ultra accuracy recommendation algorithm by considering the high-order user similarities Effect of user tastes on personalized recommendation,Why recomm

22、end,We face too much data and sources to be able to find out those most relevant for us. Indeed, we have to make choices from thousands of movies, millions of books, billions of web pages, and so on. Evaluating all these alternatives by ourselves is not feasible at all.,As a consequence, an urgent problem is how to automatically find out the relevant objects for us.,Collaborative filtering algorithm,Herlocker et al., ACM Trans. Inf. Syst. 22: 5-53 (2004),Content-based algorithm,The user will be recommended items similar to the ones this user prefer