Distributed Algorithms for the Self-organization of the Scale-free Network: Statistical Mechanics Inspired Methods

Speaker Dr. Jae-Hyun Park Chung-Ang University, Korea
CECS Host Professor Pai Chou
Location EH 3206
Date & Time October 27, 2011 Seminar begins at 11:00 AM
Abstract Recently, by physicists, it has been recognized that the scale-free network is made by a simple random process, if a kind of bias is given to purely random state of nodes in network. Because some biased physical quantities such as the availability of nodes are observed in real networks, we devise a distributed algorithm for the self-organization of the scale-free network from this discovery. Each node independently tries to connect to the best node which is superior to the node itself and all the nodes that had been connected, while the node received the request accepts it if the node asked is better than all the nodes that had been connected. Because each node deterministically finds out the candidate nodes in terms of partial order, a partial order relationship among the nodes exists. Each node working for the related algorithms uses the state information changed over time. But the node working for the proposed algorithm uses the constant observable quantity of node state so it requires only one-time broadcasting to share all the global node state data. The number of broadcast messages is tremendously diminished. We also propose a distributed algorithm for which only local node state data is used. To devise the algorithm, we analyze the scale-free network formation problem with the Statistical Mechanics, from which we show the insight that, if the degree-distribution of network is the power law, each node is adjacent to symmetric sub-graphs (or indistinguishable links).

Dr. Jae-Hyun Park received the B.S. degree in Computer Science from Chung-Ang University, Korea, in 1988, and the M.S. and Ph.D. degrees in Computer Science from the KAIST, Taejon, in 1991 and 1995, respectively. >From 1991 to 1994, as a research staff of the Satellite Research Center in KAIST, He had developed the embedded operating system for the onboard computer of KITSAT (the first Korean satellite). Especially, he had modified the Nucleus RTX Kernel (real-time operating system kernel) for dynamic process creation in a mission control on-board computer system. This works was published in the Proc. of AIAA/IEEE Digital Avionics Systems Conference. As his Ph.D. research, he did work on the fault-tolerant high-performance multistage interconnection networks for ATM switching and multiprocessing, which was published in IEEE/ACM Trans. on Networking. From 1995 to 2000, he was with the Samsung Electronics Co., Korea, where he had developed the multiprotocol label switching system over the Asynchronous Transfer Mode Switching System, including the development of the label distribution protocol, which was published in IEICE Trans. on Comm. He received the 1996 Best Research Paper Award-Golden Prize in 1997 and the 1997 Award of Excellence in Research and Development-Silver Prize in 1998, all from Samsung Electronics Co. From 2000 to 2002, he was with the School of EECS, Yeungnam University, Korea. Since 2002, he has been a professor of the School of Computer Science and Engineering, Chung-Ang University, Korea. His current research interests include switching architectures, self-organization, ad hoc networks, and scale-free networks. He is a visiting scholar at UC Irvine, hosted by Professor Pai H. Chou from February 2011 to January 2012.