PARALLELISM AND COMPLEXITY OF A SMALL-WORLD NETWORK MODEL
DOI:
https://doi.org/10.47839/ijc.15.2.840Keywords:
Random Graphs, Small-World Networks, Optimization Strategies, Deterministic, Neuronal Networks.Abstract
The small-world phenomena exhibits highly localized clustering and short-cut paths between vertices in a graph that reflect observed properties in social networks, epidemiological models and other real-world networks. The small-world models rely on the application of constraint-based randomness or the derivation of constraints on randomness to simulate the desired network complexities and their associated network connection properties. In this paper, rather than exploring the random properties of small-world networks, we employ deterministic strategies in the design of a computationally efficient distributed neuronal-axon network simulator that results in a small world network. These strategies are derived by addressing the parallel complexities of the proposed neuronal-axon network simulator, and also from physical constraints imposed by resource limitations of the distributed simulation architecture. The outcome of this study is the realization of a neuronal-axon network simulator that exhibits small-world characteristics of clustering with a logarithmic degree of separation between nodes without the need for long-range communication edges. The importance of this result is the deterministic application of reasoned optimization rules from which the small-world network emerges.References
R. Albert, H. Jeong, A.-L. Barabási, “The diameter of the World Wide Web,” Nature, vol. 401, issue 9, pp. 130-131, 1999.
R. Albert and A-L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, pp. 47-97, 2002.
B. Bollobás, Random Graphs, Academic Press, London, 1985.
I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong, “Freenet: A distributed anonymous information storage and retrieval system,” in Proceedings of the International Workshop on Design Issues in Anonymity and Unobservability, 2001, pp. 46-66.
A. R. Damasio, “Time-locked multiregional retroactivation: A system-level proposal for the neural substrates of recall and recognition,” Cognition, vol. 33, issue 1-2, pp. 25-62, 1989.
A. R. Damasio, “The brain binds entities and events by multiregional activation from convergence zones,” MIT Press, vol. 1, issue 1, pp. 123-132, 1989.
M. Denny and S. Gaines, Chance in Biology: Using Probability to Explore Nature, Princeton University Press, 2000.
P. Erdős and A. Rényi, “On random graphs,” Publicationes Mathematicae, vol. 6, pp. 290-297, 1959.
M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some simplified np-complete problems,” Theory of Computer Science, vol. 1, pp. 237-267, 1978.
W. R. Gilks, S. Richardson, and D. Spiegelhalter, Markov Chain Monte Carlo in practice, Chapman and Hall/CRC, 1996.
C. Goffman, “And what is your Erdős number?” American Mathematical Monthly, vol. 76, issue 7, p. 791, 1969.
J. Guare, Six Degrees of Separation: A Play, Vintage Books, New York, 1990.
O. Häggstrőm, Finite Markov Chains and Algorithmic Applications, Cambridge University Press, 2002.
A. L. Hodgkin and A. F. Huxley, “A quantitative description of membrane current and its application to conduction and excitation in nerve,” J. Physiol. (Lond.), vol. 117, pp. 500-544, 1952.
J. Kaiser, Ed., “It's a small Web after all,” Science, vol. 285, p. 1815, 1999.
H. Kautz, B. Selman, M. Shah, “Referral Web: combining social networks and collaborative filtering,” Communications of the ACM, vol. 30, issue 3, pp. 63-65, March 1997.
M. J. Keeling and K. T. D. Eames, “Networks and epidemic models,” J. R. Soc. Interface, vol. 2, pp. 295-307, 2005.
J. Kleinberg, “The small-world phenomenon: An algorithmic perspective,” in Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000.
D. Knoke and S. Yang, Social Network Analysis (Quantitative Applications in the Social Sciences), Sage Publications, Inc.; 2nd Edition, November 2007.
C. Korte and S. Milgram, “Acquaintance networks between racial groups: Application of the small world method,” J. Personality and Social Psych., vol. 15, pp. 101-108, 1978.
M. Kretschmar and M. Morris, “Measures of concurrency in networks and the spread of infectious disease,” Mathematical Biosciences, vol. 133, pp. 165-195, 1996.
A. Makkai and E. Jankó, Translated from Hungarian and annotated.
S. Milgram, “The small world problem,” Psychology Today, vol. 1, pp. 61-67, 1967.
M. E. Newman, “Models of the Small World,” J. Statistical Physics, vol. 101, no. 3-4, pp. 819-841, 2000.
M. E. Newman and D. J. Watts, “Renormalization group analysis of the small-world network model,” Physical Review Letters A, vol. 263, pp. 341-346, 1999.
M. E. Newman and D. J. Watts, “Scaling and percolation in the small-world network model,” Physical Review E, vol. 60, pp. 7332-7342, 1999.
O. Sandberg, “Distributed routing in small-world networks,” in Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX06), 2006.
A. Tanay, R. Sharan, M. Kupiec, and R. Shamir, “Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genome wide data,” Proceedings of National Academy of Science USA, vol. 101, issue 9, pp. 2981-2986, 2004.
J. Travers and S. Milgram, “An experimental study of the small world problem,” Sociometry, vol. 32, p. 425, 1969.
D. Watts, Small Worlds, Princeton University Press, 1999.
D. Watts and S. Strogatz, “Collective dynamics of small world networks,” Nature, vol. 393, pp. 440-442, 1998.
D. Watts, Six Degrees: The Science of a Connected Age, W.W. Norton & Co., 2003.
L. Berman, L. Carter, K. F. Day, “The fanout problem: from theory to practice,” Yorktown Height, N.Y.: IBM T.J. Watson Research Center, 1988.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
