Skip Navigation Links
Discontinuity, Nonlinearity, and Complexity

Dimitry Volchenkov (editor), Dumitru Baleanu (editor)

Dimitry Volchenkov(editor)

Mathematics & Statistics, Texas Tech University, 1108 Memorial Circle, Lubbock, TX 79409, USA


Dumitru Baleanu (editor)

Cankaya University, Ankara, Turkey; Institute of Space Sciences, Magurele-Bucharest, Romania


Improving Accuracy of Complex Network Modeling Using Maximum Likelihood Estimation and Expectation-Maximization

Discontinuity, Nonlinearity, and Complexity 3(2) (2014) 169--221 | DOI:10.5890/DNC.2014.06.006

Ehsan Jahanpour; Xin Chen

Department of Mechanical and Industrial Engineering, Southern Illinois University, Edwardsville, IL62026-1805, USA

Download Full Text PDF



Structure of a complex network provides important information about its performance and may be used to predict changes in network performance. Degree distributions are used to model the network structure. Four degree distributions, including the power law, Weibull, Poisson, and negative binomial, are applied in this research to three complex networks, the Krebs, HIV, and Power Grid networks. To improve accuracy of network modeling, the maximum likelihood estimation method and expectation-maximization algorithm are used to estimate parameters of the four degree distributions. Several statistical analyses and a simulation study are conducted to determine which degree distribution best describes the network structure. The results show that the degree distributions with two descriptive parameters, Weibull and negative binomial, provide better estimations than the onedescriptive-parameter degree distributions, power law and Poisson.


  1. [1]  D. J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness, New Jersey: Princeton University Press, 1999.
  2. [2]  S. N. Dorogovtsev and J. F. Mendes, “Evolution of Networks,” Advances in Physics, vol. 1079, p. 51, 2002.
  3. [3]  R. Albert and A.-L. Barabasi, “Statistical Mechanics of Complex Networks,” Reviews of Modern physics, vol. 74, pp. 47-97, 2002.
  4. [4]  R. Albert, H. Jeong and B. L. Albert, “Error and Attack Tolerance of Complex Networks,” Nature, vol. 406, pp. 378-382, 2000.
  5. [5]  R. Albert, H. Jeong and A.-L. Barabasi, “Diameter of the World Wide Web,” Nature, vol. 401, pp. 130-131, 1999.
  6. [6]  R. Albert, H. Jeong and A.-L. Barabasi, “Mean-Field Theory for Scale-Free Random Networks,” Physica A, vol. 272, pp. 173-187, 1999.
  7. [7]  A. Barabasi, R. Albert and H. Jeong, “Scale-free Characteristics of Random Networks: the Topology of the World Wide Web,” Physica A, vol. 281, pp. 69-77, 2000.
  8. [8]  M. Faloutsos, P. Faloutsos and C. Faloutsos, “On Power-law Relationships of the Internet Topology,” ACM SIGCOMM Computer Communication Review, vol. 29, no. 4, pp. 251-262, 1999.
  9. [9]  P. Erdos and A. Renyi, “On the Evolution of Random Graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences, vol. 5, pp. 17-61, 1960.
  10. [10]  W. Deng, W. Li, X. Cai and Q. A. Wang, “The Exponential Degree Distribution in Complex Networks: Non- Equilibrium Network Theory, Numerical Simulation and Empirical Data,” Physica A, vol. 390, no. 8, pp. 1481-1485, 2011.
  11. [11]  J.-Z. Liu and Y.-F. Tang, “An exponential distribution network,” Chinese Physics, vol. 14, no. 4, pp. 643-645, 2005.
  12. [12]  L. C. Freeman, “Centrality in Social Networks Conceptual Clarification,” Social Networks, vol. 1, pp. 215-239, 1978/79.
  13. [13]  M. E. Newman, “The mathematics of networks,” in The New Palgrave Encyclopedia of Economics, Basingstoke, Palgrave Macmillan, 2008.
  14. [14]  M. G. Everett and S. P. Borgatti, “Induced, endogenous and exogenous centrality,” Social Networks, p. 339–344, 2010.
  15. [15]  E. Jahanpour and X. Chen, “Analysis of Complex Network Performance and Heuristic Node Removal Strategies,” Communications in Nonlinear Science and Numerical Simulation, vol. 18, no. 12, pp. 3458-3468, 2013.
  16. [16]  H. S. Steven, “Exploring Complex Networks,” Nature, vol. 410, pp. 268-276, 2001.
  17. [17]  V. E. Krebs, “Mapping Networks of Terrorist Cells,” CONNECTIONS, vol. 24, no. 3, pp. 43-52, 2002.
  18. [18]  J. J. Potterat, L. Phillips-Plummer, S. Q. Muth, R. B. Rothenberg, D. E. Woodhouse, T. S. Maldonado-Long, H. P. Zimmerman and J. B. Muth, “Risk Network Structure in the Early Epidemic Phase of HIV Transmission in Colorado Springs,” Sexually Transmitted Infections, vol. 78, no. 1, pp. 159-163, 2002.
  19. [19]  D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, vol. 393, pp. 440-442, 1998.
  20. [20]  M. R. Gupta and Y. Chen, “Theory and Use of the EM Algorithm,” Foundations and Trends? in Signal Processing, vol. 4, no. 3, pp. 223-296, 2010.
  21. [21]  D. N. Moriasi, J. G. Arnold, M. W. Van Liew, R. L. Bingner, D. D. Harmel and T. L. Veith, “Model Evaluation Guidelines for Systematic Quantification of Accuracy inWatershed Simulation,” Transactions of the American Society of Agricultural and Biological Engineers, vol. 50, no. 3, pp. 885-900, 2007.
  22. [22]  R. J. Hyndman and A. B. Koehler, “Another Look at Measures of Forecast Accuracy,” International Journal of Forecasting, vol. 22, no. 4, pp. 679-688, 2006.
  23. [23]  R. Moussa, N. Chahinian and C. Bocquillon, “Distributed hydrological modelling of a Mediterranean mountainous catchment-Model construction and multi-site validation,” Journal of Hydrology, vol. 337, no. 1-2, pp. 35-51, 2007.
  24. [24]  A. Clauset, C. R. Shalizi and M. E. Newman, “Power-law distributions in empirical data,” SIAM Review, vol. 51, no. 4, pp. 661-703, 2009.
  25. [25]  V. G. Voinov and M. S. Nikulin, Unbiased Estimators and their Applications, Vol.1: Univariate Case, New York: Springer, 1993.
  26. [26]  M. A. Al-Fawzan, “Methods for Estimating the Parameters of the,” 10 2000. [Online]. Available: http://interstat. [Accessed 28 09 2012].
  27. [27]  S. J. Clark and J. N. Perry, “Estimation of the Negative Binomial Parameter K by Maximum Quasi-Likelihood,” Biometrics, vol. 45, pp. 309-316, 1989.
  28. [28]  W.W. Piegorsch, “Maximum Likelihood Estimation for the Negative Binomial Dispersion Parameter,” Biometrics, vol. 46, pp. 863-867, 1990.
  29. [29]  H. Akaike, “A New Look at the Statistical Model Identification,” IEEE Transactions on Automatic Control, vol. 19, no. 6, pp. 716-723 , 1974.
  30. [30]  S. P. Borgatti, M. G. Everett and L. C. Freeman, “Ucinet forWindows: Software for Social Network Analysis,” Analytic Technologies, 2002.
  31. [31]  R. Cohen, S. Havlin and D. Ben-Avraham, In Handbook of Graphs and Networks, Wiley, 2003, pp. 85-110.
  32. [32]  M. J. Bayarri and J. O. Berger, “The Interplay of Bayesian and Frequentist Analysis,” Statistical Science, vol. 19, no. 1, pp. 58-80, 2004.
  33. [33]  J. O. Berger and T. Sellke, “Testing a Point Null Hypothesis: The Irreconcilability of P Values and Evidence,” Journal of the American Statistical Association, vol. 82, no. 397, pp. 112-122, 1987.