A Hybrid Cuckoo Search for Direct Blockmodeling
محورهای موضوعی :Saeed NasehiMoghaddam 1 , مهدي غضنفری 2 , بابک تیمورپور 3
1 - zanjan university
2 - دانشگاه علم و صنعت
3 -
کلید واژه: Social Network Analysis (SNA) , blockmodeling , Genetic Algorithm , likelihood ratio statistics , G2, , Multi objective optimization,
چکیده مقاله :
As a way of simplifying, size reducing and making sense of the structure of each social network, blockmodeling consists of two major, essential components: partitioning of actors to equivalence classes, called positions, and clarifying relations between and within positions. Partitioning of actors to positions is done variously and the ties between and within positions can be represented by density matrices, image matrices and reduced graphs. While actor partitioning in classic blockmodeling is performed by several equivalence definitions, such as structural and regular equivalence, generalized blockmodeling, using a local optimization procedure, searches the best partition vector that best satisfies a predetermined image matrix. The need for known predefined social structure and using a local search procedure to find the best partition vector fitting into that predefined image matrix, makes generalized blockmodeling be restricted. In this paper, we formulate blockmodel problem and employ a genetic algorithm to search for the best partition vector fitting into original relational data in terms of the known indices. In addition, during multiple samples and various situations such as dichotomous, signed, ordinal or interval valued relations, and multiple relations the quality of results shows better fitness to original relational data than solutions reported by researchers in classic, generalized, and stochastic blockmodeling field.
As a way of simplifying, size reducing and making sense of the structure of each social network, blockmodeling consists of two major, essential components: partitioning of actors to equivalence classes, called positions, and clarifying relations between and within positions. Partitioning of actors to positions is done variously and the ties between and within positions can be represented by density matrices, image matrices and reduced graphs. While actor partitioning in classic blockmodeling is performed by several equivalence definitions, such as structural and regular equivalence, generalized blockmodeling, using a local optimization procedure, searches the best partition vector that best satisfies a predetermined image matrix. The need for known predefined social structure and using a local search procedure to find the best partition vector fitting into that predefined image matrix, makes generalized blockmodeling be restricted. In this paper, we formulate blockmodel problem and employ a genetic algorithm to search for the best partition vector fitting into original relational data in terms of the known indices. In addition, during multiple samples and various situations such as dichotomous, signed, ordinal or interval valued relations, and multiple relations the quality of results shows better fitness to original relational data than solutions reported by researchers in classic, generalized, and stochastic blockmodeling field.
[1] F. Lorrain and H. C. White, "Structural equivalence of individuals in social networks," The Journal of mathematical sociology, vol. 1, pp. 49-80, 1971.
[2] S. Wasserman and K. Faust, Social network analysis: Methods and applications vol. 8: Cambridge university press, 1994.
[3] P. Doreian, V. Batagelj, and A. Ferligoj, Generalized blockmodeling vol. 25: Cambridge university press, 2005.
[4] P. Doreian, V. Batagelj, and A. Ferligoj, "Generalized blockmodeling of two-mode network data," Social networks, vol. 26, pp. 29-53, 2004.
[5] P. Doreian and A. Mrvar, "Partitioning signed social networks," Social Networks, vol. 31, pp. 1-11, 2009.
[6] A. Žiberna, "Generalized blockmodeling of sparse networks," Metodoloski zvezki, vol. 10, p. 99, 2013.
[7] A. Žiberna, "Blockmodeling of multilevel networks," Social Networks, vol. 39, pp. 46-61, 2014.
[8] A. Žiberna, "Generalized blockmodeling of valued networks," Social networks, vol. 29, pp. 105-126, 2007.
[9] S. Wasserman and C. Anderson, "Stochastic a posteriori blockmodels: Construction and assessment," Social Networks, vol. 9, pp. 1-36, 1987.
[10] C. J. Anderson, S. Wasserman, and K. Faust, "Building stochastic blockmodels," Social networks, vol. 14, pp. 137-161, 1992.
[11] T. A. Snijders and K. Nowicki, "Estimation and prediction for stochastic blockmodels for graphs with latent block structure," Journal of classification, vol. 14, pp. 75-100, 1997.
[12] K. Nowicki and T. A. B. Snijders, "Estimation and prediction for stochastic blockstructures," Journal of the American Statistical Association, vol. 96, pp. 1077-1087, 2001.
[13] C. Tallberg, "A Bayesian approach to modeling stochastic blockstructures with covariates," Journal of Mathematical Sociology, vol. 29, pp. 1-23, 2004.
[14] P. D. Hoff, A. E. Raftery, and M. S. Handcock, "Latent space approaches to social network analysis," Journal of the american Statistical association, vol. 97, pp. 1090-1098, 2002.
[15] P. D. Hoff and M. D. Ward, "Modeling dependencies in international relations networks," Political Analysis, vol. 12, pp. 160-175, 2004.
[16] P. D. Hoff, "Bilinear mixed-effects models for dyadic data," Journal of the american Statistical association, vol. 100, pp. 286-295, 2005.
[17] M. S. Handcock, A. E. Raftery, and J. M. Tantrum, "Model‐based clustering for social networks," Journal of the Royal Statistical Society: Series A (Statistics in Society), vol. 170, pp. 301-354, 2007.
[18] C. Fraley and A. E. Raftery, "Model-based clustering, discriminant analysis, and density estimation," Journal of the American statistical Association, vol. 97, pp. 611-631, 2002.
[19] P. N. Krivitsky and M. S. Handcock, "latentnet: Latent position and cluster models for statistical networks," Seattle, WA. Version, vol. 2, 2007.
[20] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, "Mixed membership stochastic blockmodels," Journal of Machine Learning Research, vol. 9, pp. 1981-2014, 2008.
[21] E. P. Xing, W. Fu, and L. Song, "A state-space mixed membership blockmodel for dynamic network tomography," The Annals of Applied Statistics, vol. 4, pp. 535-566, 2010.
[22] Q. Ho, L. Song, and E. P. Xing, "Evolving cluster mixed-membership blockmodel for time-varying networks," 2011.
[23] M. Mariadassou, S. Robin, and C. Vacher, "Uncovering latent structure in valued graphs: a variational approach," The Annals of Applied Statistics, pp. 715-742, 2010.
[24] T. James, E. Brown, and C. T. Ragsdale, "Grouping genetic algorithm for the blockmodel problem," IEEE Transactions on Evolutionary Computation, vol. 14, pp. 103-111, 2010.
[25] O. C. Herfindahl, "Concentration in the steel industry," Columbia University., 1950.
[26] A. O. Hirschman, "The paternity of an index," The American Economic Review, vol. 54, pp. 761-762, 1964.
[27] M. Brusco and D. Steinley, "A tabu-search heuristic for deterministic two-mode blockmodeling of binary network matrices," Psychometrika, vol. 76, pp. 612-633, 2011.
[28] M. Brusco, P. Doreian, P. Lloyd, and D. Steinley, "A variable neighborhood search method for a two-mode blockmodeling problem in social network analysis," Network Science, vol. 1, pp. 191-212, 2013.
[29] R. L. Breiger, S. A. Boorman, and P. Arabie, "An algorithm for clustering relational data with applications to social network analysis and comparison with multidimensional scaling," Journal of mathematical psychology, vol. 12, pp. 328-383, 1975.
[30] H. C. White, S. A. Boorman, and R. L. Breiger, "Social structure from multiple networks. I. Blockmodels of roles and positions," American journal of sociology, pp. 730-780, 1976.
[31] W. de Nooy, A. Mrvar, and V. Batagelj, Exploratory Social Network Analysis with Pajek vol. 27: Cambridge University Press, 2005.
[32] S. Sampson, "Crisis in a cloister, unpublished Ph. D," Dissertation, Dept. of Sociology, Cornell University, USA, 1969.
[33] F. J. Roethlisberger and W. J. Dickson, "Management and theWorker," An Account of a Research Program conducted by theWestern Electric Co., Hawthorne Works, Chicago. HarvardUniversity Press, Cambridge, Mass, 1939.
