Discontinuity, Nonlinearity, and Complexity
Improving Accuracy of Complex Network Modeling Using Maximum Likelihood Estimation and ExpectationMaximization
Discontinuity, Nonlinearity, and Complexity 3(2) (2014) 169221  DOI:10.5890/DNC.2014.06.006
Ehsan Jahanpour; Xin Chen
Department of Mechanical and Industrial Engineering, Southern Illinois University, Edwardsville, IL620261805, USA
Download Full Text PDF
Abstract
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 expectationmaximization 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 onedescriptiveparameter degree distributions, power law and Poisson.
References

[1]  D. J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness, New Jersey: Princeton University Press, 1999. 

[2]  S. N. Dorogovtsev and J. F. Mendes, “Evolution of Networks,” Advances in Physics, vol. 1079, p. 51, 2002. 

[3]  R. Albert and A.L. Barabasi, “Statistical Mechanics of Complex Networks,” Reviews of Modern physics, vol. 74, pp. 4797, 2002. 

[4]  R. Albert, H. Jeong and B. L. Albert, “Error and Attack Tolerance of Complex Networks,” Nature, vol. 406, pp. 378382, 2000. 

[5]  R. Albert, H. Jeong and A.L. Barabasi, “Diameter of the World Wide Web,” Nature, vol. 401, pp. 130131, 1999. 

[6]  R. Albert, H. Jeong and A.L. Barabasi, “MeanField Theory for ScaleFree Random Networks,” Physica A, vol. 272, pp. 173187, 1999. 

[7]  A. Barabasi, R. Albert and H. Jeong, “Scalefree Characteristics of Random Networks: the Topology of the World Wide Web,” Physica A, vol. 281, pp. 6977, 2000. 

[8]  M. Faloutsos, P. Faloutsos and C. Faloutsos, “On Powerlaw Relationships of the Internet Topology,” ACM SIGCOMM Computer Communication Review, vol. 29, no. 4, pp. 251262, 1999. 

[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. 1761, 1960. 

[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. 14811485, 2011. 

[11]  J.Z. Liu and Y.F. Tang, “An exponential distribution network,” Chinese Physics, vol. 14, no. 4, pp. 643645, 2005. 

[12]  L. C. Freeman, “Centrality in Social Networks Conceptual Clarification,” Social Networks, vol. 1, pp. 215239, 1978/79. 

[13]  M. E. Newman, “The mathematics of networks,” in The New Palgrave Encyclopedia of Economics, Basingstoke, Palgrave Macmillan, 2008. 

[14]  M. G. Everett and S. P. Borgatti, “Induced, endogenous and exogenous centrality,” Social Networks, p. 339–344, 2010. 

[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. 34583468, 2013. 

[16]  H. S. Steven, “Exploring Complex Networks,” Nature, vol. 410, pp. 268276, 2001. 

[17]  V. E. Krebs, “Mapping Networks of Terrorist Cells,” CONNECTIONS, vol. 24, no. 3, pp. 4352, 2002. 

[18]  J. J. Potterat, L. PhillipsPlummer, S. Q. Muth, R. B. Rothenberg, D. E. Woodhouse, T. S. MaldonadoLong, 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. 159163, 2002. 

[19]  D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘SmallWorld’ Networks,” Nature, vol. 393, pp. 440442, 1998. 

[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. 223296, 2010. 

[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. 885900, 2007. 

[22]  R. J. Hyndman and A. B. Koehler, “Another Look at Measures of Forecast Accuracy,” International Journal of Forecasting, vol. 22, no. 4, pp. 679688, 2006. 

[23]  R. Moussa, N. Chahinian and C. Bocquillon, “Distributed hydrological modelling of a Mediterranean mountainous catchmentModel construction and multisite validation,” Journal of Hydrology, vol. 337, no. 12, pp. 3551, 2007. 

[24]  A. Clauset, C. R. Shalizi and M. E. Newman, “Powerlaw distributions in empirical data,” SIAM Review, vol. 51, no. 4, pp. 661703, 2009. 

[25]  V. G. Voinov and M. S. Nikulin, Unbiased Estimators and their Applications, Vol.1: Univariate Case, New York: Springer, 1993. 

[26]  M. A. AlFawzan, “Methods for Estimating the Parameters of the,” 10 2000. [Online]. Available: http://interstat. statjournals.net/YEAR/2000/articles/0010001.pdf. [Accessed 28 09 2012]. 

[27]  S. J. Clark and J. N. Perry, “Estimation of the Negative Binomial Parameter K by Maximum QuasiLikelihood,” Biometrics, vol. 45, pp. 309316, 1989. 

[28]  W.W. Piegorsch, “Maximum Likelihood Estimation for the Negative Binomial Dispersion Parameter,” Biometrics, vol. 46, pp. 863867, 1990. 

[29]  H. Akaike, “A New Look at the Statistical Model Identification,” IEEE Transactions on Automatic Control, vol. 19, no. 6, pp. 716723 , 1974. 

[30]  S. P. Borgatti, M. G. Everett and L. C. Freeman, “Ucinet forWindows: Software for Social Network Analysis,” Analytic Technologies, 2002. 

[31]  R. Cohen, S. Havlin and D. BenAvraham, In Handbook of Graphs and Networks, Wiley, 2003, pp. 85110. 

[32]  M. J. Bayarri and J. O. Berger, “The Interplay of Bayesian and Frequentist Analysis,” Statistical Science, vol. 19, no. 1, pp. 5880, 2004. 

[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. 112122, 1987. 