Volume 4 Issue 2 pp. 227-240 Spring, 2013


A novel framework in complex network analysis: Considering both structure of relations and individual characteristics in closeness centrality computation


F. Barzinpour and B. H. Ali Ahmadi




In this paper, we develop a novel framework for defining radial measures of centrality in complex networks. This framework is based on the combination of two approaches: social network analysis and traditional social science approach by considering both structure of relations and individual characteristics. It is always an important issue to detect communities in complex networks as efficiently as possible to understand both the structure and function of the networks and to interpret radial centrality measures. Therefore, we propose spectral clustering by determining the best number of communities as a prerequisite stage before finding radial measures. Based on the proposed framework, an algorithm to compute the closeness centrality in complex networks is developed. We test the proposed algorithm on Zachary’s karate club network, which is considerably used as a benchmark for community detection in a network. The preliminary results indicate that the new method is efficient at detecting both good inter-cluster closeness centrality and the appropriate number of clusters.




DOI: 10.5267/j.ijiec.2013.02.001

Keywords: Complex networks; Social network; Community structure; Spectral clustering; Closeness centrality; Node attribute

References

References Agarwal, P., Sahai, M., Mishra, V., Bag, M., & Singh, V. (2011). A review of multi-criteria decision making techniques for supplier evaluation and selection.International Journal of Industrial Engineering Computations, 2, 801-810.

Arenas, A., Fernández, A., & Gómez, S. (2008). Analysis of the structure of complex networks at different resolution levels.New Journal of Physics, 10 (5), 053039.

Bidart, C., & Lavenu, D. (2005).Evolutions of personal networks and life events. Social Networks, 27, 359-376.

Bonacich, P. (1987). Power and centrality: a family of measures. American Journal of Sociology, 92, 1170-1182.

Borgatti, S. P., & Everett, M. G. (1999).Network Analysis of 2-Mode Data. Social Networks, 19, 243-269.

Borgatti, S. P., & Everett, M. G. (2006).A Graph-theoretic perspective on centrality. Social Networks, 28, 466-484.

Borgatti, S. P., Carley, K. M., & Krackhardt, D. (2006). On the robustness of centrality measures under conditions of imperfect data. Social Networks, 28, 124-136.

Danon, L., Duch, J., Diaz-Guilera, A., & Arenas, A. (2005). Comparing community structure identification. Journal of Statistical Mechanics, 09008.

Donetti, L., & Muñoz, M.A. (2004).Detecting network communities: a new systematic and efficient algorithm. Journal of Statistical Mechanics, 10012.

Duch, J., & Arenas, A. (2005). Community detection in complex networks using external optimization. Physics Review E, 72, 027104.

E, W., Li, T., & Vanden-Eijnden, E. (2008). Optimal partition and effective dynamics of complex networks. Proceeding of the National Academy of Sciences USA, 105 (23), 7907-7912.

Estrada,E. (2011).Community detection based on network communicability. Chaos, 21, 016103.

Estrada, E., & Rodrı´guez-Vela´ zquez, J. A. (2006).Subgraph centrality and clustering in complex hyper-networks. Physica A, 364, 581-594.

Fortunato, S., (2010). Community detection in graphs. Physics Reports, 486, 75-174.

Fortunato, S., Latora, V., & Marchiori, M. (2004). Method to find community structures based on information centrality. Physics Review E, 70, 056104.

Freeman, L. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1, 215-239.

Ghosh, T., Sengupta, S., Chattopadhyay, M., & Dan, P. K. (2010). Meta-heuristics in cellular manufacturing: A state-of-the-art review. International Journal of Industrial Engineering Computations.

Girvan, M. & Newman, M. (2002).Community structure in social and biological networks. Proceeding of the National Academy of Sciences USA,99 (12), 7821-7826.

Guzman, M. (2008).A probabilistic programming approach in the analysis of social networks, Master thesis, University of Arkansas, Arkansas.

Hu, H., & Wang, X. (2012). How people make friends in social networking sites—A microscopic Perspective. Physica A, 391, 1877.

Jabal-Ameli, M. S., Aryanezhad, M. B., & Ghaffari-Nasab, N. (2011). A variable neighborhood descent based heuristic to solve the capacitated location-routing problem. International Journal of Industrial Engineering Computations, 2(1), 141-154.

Kaza,S.(2008).Instance, evolution, and predictive modeling of social networks, PhD thesis, The University of Arizona.

Kuhnert,M. T.,Geier, C.,& Elger, C. E. (2012). Identifying important nodes in weighted functional brain networks: A comparison of different centrality approaches.Chaos, 22, 023142.

Li, T., Liu, J.,& E., W. (2009).Probabilistic framework for network partition.Physics Review E, 80, 026106.

Lippert, S., Spagnolo, G. (2011).Networks of relations and Word-of-Mouth Communication. Games and Economic Behavior, 72, 202-217.

Liu,C. (2011).The effects of innovation alliance on network structure and density of cluster.Expert Systems with Applications, 38, 299-305.

Liu,J., & Liu, T. (2010).Detecting community structure in complex networks using simulated annealing with k-means algorithms. Physica A, 389, 2300-2309.

Louch, H. (2000). Personal network integration: transitivity and homophily in strong-tie relations, Social Networks, 22, 45-64.

Ma, X., Gao, L., Yong, X., & Fu, L. (2010).Semi-supervised clustering algorithm for community structure detection in complex networks. Physica A, 389, 187-197.

Mahmoudi, M., & Sapiro, G. (2009). Three-dimensional point cloud recognition via distributions of geometric distances. Graphical Models, 71, 22–31.

Mello, B.A., Batistuta, L.H., Boueri, R., & Cajueiro, D.O. (2009).Measuring the flow of information among cities using the diffusion power.Physics Letters A, 374, 126-130.

Newman, M. (2004). Detecting community structure in networks. European Physical Journal B, 38, 321-330.

Newman, M., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physics Review E, 69 (2), 026113.

Newman, M. (2006a). Finding community structure in networks using the eigenvectors of matrices. Physics Review E, 74, 036104.

Newman, M. (2006b).Modularity and community structure in networks. Proceeding of the National Academy of Sciences USA, 103 (23), 8577-8582.

Nieminen, J. (1974). On centrality in a graph. Scandinavian Journal of Psychology, 15, 322-336.

Niu, Y. Q., Hu, B. Q., Zhang, W., & Wang, M. (2008).Detecting the community structure in complex networks based on quantum mechanics. Physica A, 387, 6215-6224.

Pollner, P., Palla, G., Ábel, D., Vicsek, A., Farkas, I. J., Derényi, I., & Vicsek, T. (2008).Centrality properties of directed module members in social networks. Physica A, 387, 4959-4966.

Radicchi, F., Castellano, C., Cecconi, F., Loreto, V.& Parisi, D. (2004).Proceeding of the National Academy of Sciences USA, 101, 2658-2663.

Reagans,R. (1998). Differences in social difference: examining third party effects on relational stability.Social Networks, 20, 143-157.

Reichardt, J., & Bornholdt,S. (2004).Detecting fuzzy community structures in complex networks with a Potts model.Physical Review Letters, 93, 218701.

Sabidussi, G. (1966). The centrality index of a graph. Psychometrika, 31, 581-603.

Simon, F., & Tellier, A. (2011). How do actors shape social networks during the process of new product development? European Management Journal, 29, 414-430.

Totterdell, P., Holman, D., & Hukin, A. (2008).Social networkers: Measuring and examining individual differences in propensity to connect with others. Social Networks, 30, 283-296.

Valente, T. W., & Foreman, R. K.(1998).Integration and radiality: measuring the extent of an individual`s connectedness and reachability in a network. Social Networks, 20, 89-105.

Wasserman, S., & Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge:Cambridge University Press.

Wu, F., & Huberman, B.A. (2004). Finding communities in linear time: a physics approach. European Physical Journal B, 38, 331-338.

Yen, L., Fouss, F., Decaestecker, C., Francq, P., & Saerens, M. (2009). Graph nodes clustering with the sigmoid commute-time kernel: A comparative study.Data and Knowledge Engineering, 68, 338-361.

Zachary, W. (1977).An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33 (4), 452-473.

Zhang, S., Wang, R., & Zhang, X. (2007). Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A, 374, 483-490.

Zhang, J., Zhang, S.,& Zhang, X. (2008). Detecting community structure in complex networks based on a measure of information discrepancy. Physica A, 387, 1675-1682.

Zhang, J., Xu, X., Li, P., Zhang, K., & Small, M. (2011). Node importance for dynamical process on networks: A multiscale Characterization. Chaos, 21, 016107.

Zhou, H. (2003). Distance, dissimilarity index, and network community structure, Physics Review E, 67 (6), 061901.