Institutional Repository
| principles of network computing | |
| Pan Yicheng | |
| 2012 | |
| Conference Name | 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 |
| Source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Pages | 30-39 |
| Conference Date | May 16, 2012 - May 21, 2012 |
| Conference Place | Beijing, China |
| Indexed Type | EI ; SPRINGER |
| ISSN | 0302-9743 |
| ISBN | 9783642299513 |
| Department | (1) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences China |
| English Abstract | In the new century, the study of networks is being developed rapidly. Traditional algorithms based on the classical graph theory have not been able to cope with large scaled networks due to their inefficiency. In this paper, we review the research on the question why a huge network such as the www-network is efficiently computable, and investigate the principles of network computing. Networks cannot be fully and exactly computed due to both their nature and their scales. The best possibility of network computing could be just locally testable graph properties, in sparse graph models. We review the progress of the study of graph property test, in particular, local test of conductance of graphs, which is closely related to the basic network structural cells - small communities. In the past decade, an avalanche of research has shown that many real networks, independent of their age, function, and scope, converge to similar architectures, which is probably the most surprising discovery of modern network theory. In many ways, there is a need to understand the dynamics of the processes that take place in networks. We propose a new local mechanism by introducing one more dimension for each node in a network and define a new model of networks, the homophily model, from which we are able to prove the homophily theorem that implies the homophily law of networks. The homophily law ensures that real world networks satisfies the small community phenomenon, and that nodes within a small community share some remarkable common features. © 2012 Springer-Verlag.; In the new century, the study of networks is being developed rapidly. Traditional algorithms based on the classical graph theory have not been able to cope with large scaled networks due to their inefficiency. In this paper, we review the research on the question why a huge network such as the www-network is efficiently computable, and investigate the principles of network computing. Networks cannot be fully and exactly computed due to both their nature and their scales. The best possibility of network computing could be just locally testable graph properties, in sparse graph models. We review the progress of the study of graph property test, in particular, local test of conductance of graphs, which is closely related to the basic network structural cells - small communities. In the past decade, an avalanche of research has shown that many real networks, independent of their age, function, and scope, converge to similar architectures, which is probably the most surprising discovery of modern network theory. In many ways, there is a need to understand the dynamics of the processes that take place in networks. We propose a new local mechanism by introducing one more dimension for each node in a network and define a new model of networks, the homophily model, from which we are able to prove the homophily theorem that implies the homophily law of networks. The homophily law ensures that real world networks satisfies the small community phenomenon, and that nodes within a small community share some remarkable common features. © 2012 Springer-Verlag. |
| Keyword | Artificial Intelligence |
| Sponsorship | State Key Laboratory of Computer Science; Chinese Academy of Sciences, Institute of Software; Chinese Academy of Sciences |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/15727 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Pan Yicheng. principles of network computing[C],2012:30-39. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment