CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Systematic Review on Complex Networks and its Performance Evaluation Metrics

by Selasie A. Brown, Patrick Kudjo, Francis Amavi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 175 - Number 13
Year of Publication: 2020
Authors: Selasie A. Brown, Patrick Kudjo, Francis Amavi
10.5120/ijca2020920614

Selasie A. Brown, Patrick Kudjo, Francis Amavi . A Systematic Review on Complex Networks and its Performance Evaluation Metrics. International Journal of Computer Applications. 175, 13 ( Aug 2020), 27-37. DOI=10.5120/ijca2020920614

@article{ 10.5120/ijca2020920614,
author = { Selasie A. Brown, Patrick Kudjo, Francis Amavi },
title = { A Systematic Review on Complex Networks and its Performance Evaluation Metrics },
journal = { International Journal of Computer Applications },
issue_date = { Aug 2020 },
volume = { 175 },
number = { 13 },
month = { Aug },
year = { 2020 },
issn = { 0975-8887 },
pages = { 27-37 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume175/number13/31514-2020920614/ },
doi = { 10.5120/ijca2020920614 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:24:57.560720+05:30
%A Selasie A. Brown
%A Patrick Kudjo
%A Francis Amavi
%T A Systematic Review on Complex Networks and its Performance Evaluation Metrics
%J International Journal of Computer Applications
%@ 0975-8887
%V 175
%N 13
%P 27-37
%D 2020
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The rapid advancement in computer systems has generated an increasing interest in the study and analysis of complex networks and its applications in the real world. Previous studies on complex networks have mainly been focused on investigating and presenting theories and concepts that explain the basic models such as regular graphs, random graphs, small-world networks, and scale-free networks with its application in the field of business, sociology, biology, immunology, and technology. In order to better comprehend the recent progress in complex systems, this paper reviews extensively, the current progress made towards complex network analysis by exploring four core aspects of complex network. The fundamental aspects reviewed are Random Graph, Scale-Free, Biological Networks, and Small World. Additionally, an in-depth analysis of the theoretical models, tools, techniques, and evaluation metrics applied in previous studies are presented. Finally, the paper provides a thorough analysis of complex network, report some related works, and attempt to address some challenges associated with using discrete-event simulators for performance evaluation of complex networks.

References
  1. X. F. Wang and G. Chen, "Complex networks: small-world, scale-free and beyond," IEEE Circuits and systems magazine, vol. 3, pp. 6-20, 2003.
  2. D. B. West, Introduction to graph theory vol. 2: Prentice hall Upper Saddle River, 2001.
  3. Euler, "Historical Notes," Substance P. Raven Press, New York, NY, pp. 1-3, 1977.
  4. B. Mohar and C. Thomassen, Graphs on surfaces vol. 2: JSTOR, 2001.
  5. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, "Complex networks: Structure and dynamics," Physics Reports, vol. 424, pp. 175-308, 2006.
  6. M. E. Newman, "The structure and function of complex networks," SIAM review, vol. 45, pp. 167-256, 2003.
  7. G. Chen, X. Wang, and X. Li, Introduction to complex networks: models, structures, and dynamics: Higher Education Press, 2012.
  8. D. J. Watts and S. H. Strogatz, "Collective dynamics of ‘small-world’networks," Nature, vol. 393, pp. 440-442, 1998.
  9. H. Wang and Y. Guo, "Consensus on scale-free network," in American Control Conference, 2008, 2008, pp. 748-752.
  10. A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, pp. 509-512, 1999.
  11. S. N. Dorogovtsev and J. F. Mendes, "Evolution of networks," Advances in Physics, vol. 51, pp. 1079-1187, 2002.
  12. J. B. Holthoefer, "Semantic networks and cognitive dynamics," Universitat Rovira i Virgili, 2011.
  13. X. F. Liu and C. K. Tse, "A General Framework for Complex Network Applications," arXiv preprint arXiv:1507.05687, 2015.
  14. J. P. Bagrow, Analysis, and applications of complex networks, 2008.
  15. L. Lü and T. Zhou, "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, vol. 390, pp. 1150-1170, 2011.
  16. R. Pastor-Satorras and A. Vespignani, Evolution and structure of the Internet: A statistical physics approach: Cambridge University Press, 2007.
  17. S. Milgram, "The small world problem," Psychology Today, vol. 2, pp. 60-67, 1967.
  18. C. Korte and S. Milgram, "Acquaintance networks between racial groups: Application of the small world method," Journal of personality and social psychology, vol. 15, p. 101, 1970.
  19. K. Klemm and V. M. Eguiluz, "Growing scale-free networks with small-world behavior," Physical Review E, vol. 65, p. 057102, 2002.
  20. S. Wasserman and K. Faust, Social network analysis: Methods and applications vol. 8: Cambridge University press, 1994.
  21. S. Achard and E. Bullmore, "Efficiency and cost of economical brain functional networks," PLoS Comput Biol, vol. 3, p. e17, 2007. Q. K. Telesford, K. E. Joyce, S. Hayasaka, J. H. Burdette, and P.
  22. J. Laurienti, "The ubiquity of small-world networks," Brain connectivity, vol. 1, pp. 367-375, 2011.
  23. V. Latora and M. Marchiori, "Efficient behavior of small-world networks," Physical review letters, vol. 87, p. 198701, 2001.
  24. A.-L. Barabási, "Scale-free networks: a decade and beyond," science, vol. 325, pp. 412-413, 2009.
  25. S. Tao, S. Wang, Y. Jiang, and L. Zhu, "Self-similarity Research on Scale-free Networks," in Networking, Sensing and Control, 2008. ICNSC 2008. IEEE International Conference on, 2008, pp. 429-432.
  26. L. Zhang, M. Small, and K. Judd, "Exactly scale-free scale-free networks," Physica A: Statistical Mechanics and its Applications, vol. 433, pp. 182-197, 2015.
  27. L. A. Adamic and B. A. Huberman, "Power-law distribution of the world wide web," Science, vol. 287, pp. 2115-2115, 2000.
  28. R. Cohen and S. Havlin, "Scale-free networks are ultra-small," Physical review letters, vol. 90, p. 058701, 2003.
  29. Erd6s and A. Rényi, "On the evolution of random graphs," Publ. Math. Inst. Hungar. Acad. Sci, vol. 5, pp. 17-61, 1960.
  30. M. Boguná, R. Pastor-Satorras, and A. Vespignani, "Absence of epidemic threshold in scale-free networks with degree correlations," Physical review letters, vol. 90, p. 028701, 2003.
  31. R. Van Der Hofstad, "Random graphs and complex networks," Available on http://www. win. tue. nl/rhofstad/NotesRGCN. pdf, p. 11, 2009.
  32. M. E. Newman, "Random graphs as models of networks," arXiv preprint condmat/0202208, 2002.
  33. E. N. Gilbert, "Random graphs," The Annals of Mathematical Statistics, vol. 30, pp. 1141-1144, 1959.
  34. M. Penrose, Random geometric graphs: Oxford University Press, 2003.
  35. B. Bollobás and O. Riordan, "Coupling scale-free and classical random graphs," Internet Mathematics, vol. 1, pp. 215-225, 2004.
  36. P. Erdos and A. Rényi, "On the evolution of random graphs," Bull. Inst. Internet Statist, vol. 38, pp. 343-347, 1961.
  37. M. E. Newman, S. H. Strogatz, and D. J. Watts, "Random graphs with arbitrary degree distributions and their applications," Physical review E, vol. 64, p. 026118, 2001.
  38. J. E. Hopcroft and R. M. Karp, "An n^5/2 algorithm for maximum matchings in bipartite graphs," SIAM Journal on computing, vol. 2, pp. 225-231, 1973.
  39. G. Robins, P. Pattison, Y. Kalish, and D. Lusher, "An introduction to exponential random graph (p*) models for social networks," Social networks, vol. 29, pp. 173-191, 2007.
  40. T. A. Snijders, "Markov chain Monte Carlo estimation of exponential random graph models," Journal of Social Structure, vol. 3, pp. 1-40, 2002.
  41. D. S. Callaway, M. E. Newman, S. H. Strogatz, and D. J. Watts, "Network robustness and fragility: Percolation on random graphs," Physical review letters, vol. 85, p. 5468, 2000.
  42. L. Cao, "Data science: a comprehensive overview," Submitted to ACM Computing Survey, pp. 1-37, 2016.
  43. J. Ellson, E. Gansner, L. Koutsofios, S. C. North, and G. Woodhull, "Graphviz—open source graph drawing tools," in International Symposium on Graph Drawing, 2001, pp. 483-484.
  44. E. R. Gansner, "Drawing graphs with Graphviz," Technical report, AT&T Bell Laboratories, Murray, Tech. Rep2009.
  45. P. Shannon, A. Markiel, O. Ozier, N. S. Baliga, J. T. Wang, D. Ramage, et al., "Cytoscape: a software environment for integrated models of biomolecular interaction networks," Genome research, vol. 13, pp. 2498-2504, 2003.
  46. M. Bastian, S. Heymann, and M. Jacomy, "Gephi: an open source software for exploring and manipulating networks," ICWSM, vol. 8, pp. 361-362, 2009.
  47. W. Lu, X. Li, and Z. Rong, "Global stabilization of complex networks with digraph topologies via a local pinning algorithm," Automatica, vol. 46, pp. 116-121, 2010.
  48. R. Van Den Brink and R. P. Gilles, "Measuring domination in directed networks," Social Networks, vol. 22, pp. 141-157, 2000.
  49. G. Yan, T. Zhou, B. Hu, Z.-Q. Fu, and B.-H. Wang, "Efficient routing on complex networks," Physical Review E, vol. 73, p. 046108, 2006.
  50. R. Olfati-Saber and R. M. Murray, "Consensus problems in networks of agents with switching topology and time-delays," IEEE Transactions on automatic control, vol. 49, pp. 1520-1533, 2004.
  51. R. Guimera, M. Sales-Pardo, and L. A. N. Amaral, "Modularity from fluctuations in random graphs and complex networks," Physical Review E, vol. 70, p. 025101, 2004.
  52. L. d. F. Costa, O. N. Oliveira Jr, G. Travieso, F. A. Rodrigues, P.R. Villas Boas, L. Antiqueira, et al., "Analyzing and modeling real- world phenomena with complex networks: a survey of applications," Advances in Physics, vol. 60, pp. 329-412, 2011.
  53. C. Li, H. Wang, W. De Haan, C. Stam, and P. Van Mieghem, "The correlation of metrics in complex networks with applications in functional brain networks," Journal of Statistical Mechanics: Theory and Experiment, vol. 2011, p. P11018, 2011.
  54. J. Brody, "Rebels, Deviants, and Individualists... Reactions to Psychology: An Evolutionary Ap-proach. By Steven Gaulin & Donald McBurney, 2001, Upper Saddle River, NJ: Prentice Hall, 13 chapters, 402 pages."
  55. F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, and Y. Åberg, "The web of human sexual contacts," Nature, vol. 411, pp. 907-908, 2001.
  56. X. Guardiola, R. Guimera, A. Arenas, A. Diaz-Guilera, D. Streib, and L. Amaral, "Macro-and micro-structure of trust networks," arXiv preprint cond-mat/0206240, 2002.
  57. M. Boguñá, R. Pastor-Satorras, A. Díaz-Guilera, and A. Arenas, "Models of social networks based on social distance attachment," Physical review E, vol. 70, p. 056122, 2004.
  58. P. Zakharov, "Diffusion approach for community discovering within the complex networks: LiveJournal study," Physica A: Statistical Mechanics and its Applications, vol. 378, pp. 550-560, 2007.
  59. P. M. Gleiser and L. Danon, "Community structure in jazz," Advances in complex systems, vol. 6, pp. 565-573, 2003.
  60. C. Nextmedia, "Social Networks Overview: Current Trends and Research Challenges," European Commission Information Society and Media, 2010.
  61. T. G. Armstrong, V. Ponnekanti, D. Borthakur, and M. Callaghan, "LinkBench: a database benchmark based on the Facebook social graph," in Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, 2013, pp. 1185- 1196.
  62. Y. Yamaguchi, T. Takahashi, T. Amagasa, and H. Kitagawa, "Turank: Twitter user ranking based on user-tweet graph analysis," in International Conference on Web Information Systems Engineering, 2010, pp. 240-253.
  63. J. Ugander, B. Karrer, L. Backstrom, and C. Marlow, "The anatomy of the facebook social graph," arXiv preprint arXiv:1111.4503, 2011.
  64. A. Bonato and Y. Tian, "Complex networks and social networks," in Advances in Network Analysis and its Applications, ed: Springer, 2012, pp. 269-286.
  65. A. V. Nefian and M. H. Hayes III, "Hidden Markov models for face recognition," choice, vol. 1, p. 6, 1998.
  66. W. W. Goh, Y. H. Lee, M. Chung, and L. Wong, "How advancement in biological network analysis methods empowers proteomics," Proteomics, vol. 12, pp. 550-563, 2012.
  67. H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási, "The large-scale organization of metabolic networks," Nature, vol. 407, pp. 651-654, 2000.
  68. R. Overbeek, N. Larsen, G. D. Pusch, M. D’Souza, E. Selkov Jr, N. Kyrpides, et al., "WIT: integrated system for high-throughput genome sequence analysis and metabolic reconstruction," Nucleic acids research, vol. 28, pp. 123-125, 2000.
  69. D. A. Fell and A. Wagner, "The small world of metabolism," Nature biotechnology, vol. 18, pp. 1121-1122, 2000.
  70. J. Zhao, H. Yu, J. Luo, Z. Cao, and Y. Li, "Complex networks theory for analyzing metabolic networks," Chinese Science Bulletin, vol. 51, pp. 1529-1537, 2006.
  71. R. Albert, H. Jeong, and A.-L. Barabási, "Error and attack tolerance of complex networks," nature, vol. 406, pp. 378-382, 2000.
  72. J. Stelling, U. Sauer, Z. Szallasi, F. J. Doyle, and J. Doyle, "Robustness of cellular functions," Cell, vol. 118, pp. 675-685, 2004.
  73. H. Kitano, "Biological robustness," Nature Reviews Genetics, vol. 5, pp. 826-837, 2004.
  74. J.-C. Rain, L. Selig, H. De Reuse, V. Battaglia, C. Reverdy, S. Simon, et al., "The protein–protein interaction map of Helicobacter pylori," Nature, vol. 409, pp. 211-215, 2001.
  75. L. Giot, J. S. Bader, C. Brouwer, A. Chaudhuri, B. Kuang, Y. Li, et al., "A protein interaction map of Drosophila melanogaster," science, vol. 302, pp. 1727-1736, 2003.
  76. V. Colizza, A. Flammini, A. Maritan, and A. Vespignani, "Characterization and modeling of protein–protein interaction networks," Physica A: Statistical Mechanics and its Applications, vol. 352, pp. 1-27, 2005.
  77. A. Wagner and D. A. Fell, "The small world inside large metabolic networks," Proceedings of the Royal Society of London B: Biological Sciences, vol. 268, pp. 1803-1810, 2001.
  78. S. Wuchty, "Interaction and domain networks of yeast," Proteomics, vol. 2, pp. 1715-1723, 2002.
  79. J.-F. Rual, K. Venkatesan, T. Hao, T. Hirozane-Kishikawa, A. Dricot, N. Li, et al., "Towards a proteome-scale map of the human protein–protein interaction network," Nature, vol. 437, pp. 1173- 1178, 2005.
  80. J. Cohen, F. Briand, and C. Newman, Community food webs: data and theory vol. 20: Springer Science & Business Media, 2012.
  81. J. M. Montoya and R. V. Solé, "Small world patterns in food webs," Journal of theoretical biology, vol. 214, pp. 405-412, 2002.
  82. Y. Moreno, L. M. Floría, and J. Gómez-Gardeñes, "Current trends in the modeling of biological networks," in From Physics to Biology: the interface between experiment and cumputation(AIP Conference Proceedings), 2006, pp. 150-161.
  83. L. Ellwardt, T. G. Van Tilburg, and M. J. Aartsen, "The mix matters: Complex personal networks relate to higher cognitive functioning in old age," Social Science & Medicine, vol. 125, pp. 107-115, 2015.
  84. T. G. Crainic, "Service network design in freight transportation," European Journal of Operational Research, vol. 122, pp. 272-288, 2000.
  85. Y. LI, W. ZHOU, and S.-j. GUO, "An Analysis of Complexity of Public Transportation Network in Shanghai [J]," Systems Engineering, vol. 1, p. 006, 2007.
  86. R. Albert, H. Jeong, and A.-L. Barabási, "Internet: Diameter of the world-wide web," Nature, vol. 401, pp. 130-131, 1999.
  87. F. Strozzi and C. Colicchia, "Literature review on complex network methods applied to measure robustness in supply chain design," Liuc Papers, 2012.
  88. P. Pons and M. Latapy, "Computing communities in large networks using random walks," in International Symposium on Computer and Information Sciences, 2005, pp. 284-293.
  89. A. Babus, "The formation of financial networks," The RAND Journal of Economics, vol. 47, pp. 239-272, 2016.
  90. L. d. F. Costa, F. A. Rodrigues, G. Travieso, and P. R. Villas Boas, "Characterization of complex networks: A survey of measurements," Advances in physics, vol. 56, pp. 167-242, 2007.
  91. G. Lima-Mendez and J. van Helden, "The powerful law of the power law and other myths in network biology," Molecular BioSystems, vol. 5, pp. 1482-1493, 2009.
  92. J. C. Reijneveld, S. C. Ponten, H. W. Berendse, and C. J. Stam, "The application of graph theoretical analysis to complex networks in the brain," Clinical Neurophysiology, vol. 118, pp. 2317-2331, 2007.
  93. L. da Fontoura Costa, M. P. Viana, and M. E. Beletti, "Complex channel networks of bone structure," Applied physics letters, vol. 88, p. 033903, 2006.
  94. Y. Sun, L. Ma, A. Zeng, and W.-X. Wang, "Spreading to localized targets in complex networks," Scientific Reports, vol. 6, p. 38865, 2016.
  95. M. Steyvers and J. B. Tenenbaum, "The Large‐ scale structure of semantic networks: Statistical analyses and a model of semantic growth," Cognitive science, vol. 29, pp. 41-78, 2005.
  96. Anastasi, Giuseppe, Alessio Falchi, Andrea Passarella, Marco Conti, and Enrico Gregori. "Performance measurements of motes sensor networks." In Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, pp. 174-181. ACM, 2004.
  97. C. Intanagonwiwat, R. Govindan, D. Estrin, “Directed diffusion: a scalable and robust communication paradigm for sensor networks”, Proceedings of the International Conference on Mobile Computing and Networking (Mobicom 2000), August 6 - 11, 2000, Boston (MA)
  98. Y. Sankarasubramaniam, O. Akan, I. Akyildiz, “ESRT: Event-to- Sink Reliable Transport in Wireless Sensor Networks” Proc. of the ACM MobiHoc Conference, Annapolis, Maryland, June 2003.
  99. C. Wan, A. Campbell, L. Krishnamurthy, "PSFQ: A Reliable Transport Protocol for Wireless Sensor Networks," First Workshop on Sensor Networks and Applications (WSNA), September 2002, Atlanta, GA.
  100. C. Wan, S. B. Eisenman, A.T. Campbell, "CODA: Congestion Detection and Avoidance in Sensor Networks," ACM SenSys, 2003.
  101. A. Woo, D. Culler, “A transmission control scheme for media access in sensor networks”, Proceedings of the International conference on Mobile Computing and Networking (Mobicom 2001), Rome (Italy) D. S. Bernstein, Z. Feng, B. N. Levine, and S. Zilberstein. Adaptive Peer Selection. In Proc. of Second International Workshop on Peer-to-Peer Systems, Berkeley, CA, USA, 2003. Springer, LNCS 2735
  102. M. Ripeanu, I. Foster, and A. Iamnitchi. Mapping the Gnutella Network: Properties of large-scale peer-to-peer systems and implications for system design. IEEE Internet Computing, 6(1):50– 57, jan-feb 2002.
  103. S. Saroiu, P. K. Gummadi, and S. D. Gribble. A Mesaurement Study of Peer-to-Peer File Sharing System. In Proceedings of Multimedia Computing and Networking (MMCN) 2002, Jan 2002.
  104. D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex Behavior at Scale: An Experimantal Study of LowPower Wireless Sensor Networks. Technical Report CSD-TR 02-0013, UCLA.
  105. S. Saroiu, P. K. Gummadi, and S. D. Gribble. A Mesaurement Study of Peer-to-Peer File Sharing System. In Proceedings Of Multimedia Computing and Networking (MMCN) 2002, Jan 2002
  106. M. Ripeanu, I. Foster, and A. Iamnitchi. Mapping the Gnutella Network: Properties of large-scale peer-to-peer systems and implications for system design. IEEE Internet Computing, 6(1):50– 57, jan-feb 2002.
  107. D. Stutzbach and R. Rejaie. Characterizing Churn in Peer-to-Peer Networks. Technical report, 2005. Technical Report CIS-TR- 2005-03 University of Oregon
  108. D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex Behavior at Scale: An Experimental Study of LowPower Wireless Sensor Networks. Technical Report CSD-TR 02-0013, UCLA.
  109. Banks J., Carson J., Nelson B., & Nicol D. (2001). Discrete- Event System Simulation. Prentice Hall. 3. ISBN 0-13-088702-1.
  110. Zhao, Yu, et al. "Fault Modeling and Simulation Based on Cyber Physical System in Complex Distribution Network." 2018 China International Conference on Electricity Distribution (CICED). IEEE, 2018.
  111. Nayyar, Anand, and Valentina Emilia Balas. "Analysis of simulation tools for underwater sensor networks (UWSNs)." International Conference on Innovative Computing and Communications. Springer, Singapore, 2019.
  112. Fall, K. and Varadhan, K. The ns Manual (formerly ns Notes and Documentation). The VINT project, 47.2015. Available at: https://www.isi.edu/nsnam/ns/doc/ns_doc.pdf [Last Access: May 8, 2019]
  113. Korkalainen, M., Sallinen, M., Kärkkäinen, N. and, Tukeva, P., “Survey of wireless sensor networks simulation tools for demanding applications”. In proc. of the Fifth International Conference on Networking and Services (ICNS'09). April 20-25, 2009. Valencia, Spain (pp. 102-106). DOI: 10.1109/ICNS.2009.75
  114. Omnet++ Network simulator. Available at: https://www.omnetpp.org/ [Last Access: May 8, 2019]
  115. E. Mota, A. Wolisz, and K. Pawlikowski, "A perspective of batching methods in a simulation environment of multiple replications in parallel " presented at the 32nd Conference on Simulation Orlando, Florida 2000, pp. 761-766.
  116. The NetSim, Available at http://en.wikipedia.org/wiki/NetSim. [Last Access: May 8, 2019]
Index Terms

Computer Science
Information Sciences

Keywords

Complex Network Random Graph Biological Networks Small World Social Network Network Simulators

Powered by PhDFocusTM