从瑞士数学家欧拉解决七桥问题开始,引申出拓扑学和图论诞生的原理,总结回顾了网络科学从规则网络到随机网络再到复杂网络的发展历程,阐述了网络科学的内涵,讨论了网络科学与其他学科的交叉,最后指出了网络科学发展中面临的4个方面的数学挑战问题:即复杂性新的拓扑表示理论;千万亿级稀疏网络的计算技术;大规模网络结构的动力学行为及不同层次混杂网络的融合机理。
This paper starts from the seven bridges problem solved by Euler, and extends the principles of topology and graph theory. Then we give a review of the network sciences development from regular networks to random networks and then to complex networks, expounding the connotation of network sciences and discussing the cross with other disciplines. Finally, we point out four aspects of mathematical challenges including the new topological representation theory of complexity, computing technology of million level of sparse networks, dynamic behavior of large scale network structure, and aggregation mechanism of different levels hybrid networks.
[1] Euler L. The seven bridges of Konigsberg[M]. Germany: Wm Benton, 1956.
[2] ERDdS P, R&WI A. On random graphs I[J]. Publ Math Debrecen, 1959, 6: 290-297.
[3] Bollobás B. Random Graphs[M]. Cambridge: Cambridge University Press, 2001.
[4] Watts D J. Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998,393 (6684): 440-442.
[5] Travers J, Milgram S. An experimental study of the small world problem[J]. Sociometry, 1969,32: 425-443.
[6] Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[7] Albert R, Jeong H, Barabási A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406(6794): 378-382.
[8] Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
[9] Barabasi A L. Linked: The New Science of Networks[M]. New York: Perseus Books Group, 2002.
[10] Watts D J. The“ new” science of networks[J]. Annual Review of Sociology, 2004,30: 243-270.
[11] Moore C, Newman M E J. Epidemics and percolation in small-world networks[J]. Physical Review E, 2000, 61(5): 5678.
[12] Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks[J]. Physical Review Letters, 2001, 86(14): 3200-3203.
[13] Shannon C E. A mathematical theory of communication[J]. The Bell System Technical Journal, 1948, 27: 379-423, 623-656.
[14] Muthukrishnan S. Massive data streams research: where to go[R]. Thomas Davis: Tech Rep Rutgers University, 2010.
[15] Papadopoulos F, Kitsak M, Serrano M á, et al. Popularity versus similarity in growing networks[J]. Nature, 2012, 489(7417): 537-540.
