2015
Conference article
Open Access
Distributed Current Flow Betweenness Centrality
Lulli A., Ricci L., Carlini E. Dazzi P.
Graph Processing Distributed Algorithms
The computation of nodes centrality is of great importance for the analysis of graphs. The current flow betweenness is an interesting centrality index that is computed by considering how the information travels along all the possible paths of a graph. The current flow betweenness exploits basic results from electrical circuits, i.e. Kirchhoff's laws, to evaluate the centrality of vertices. The computation of the current flow betweenness may exceed the computational capability of a single machine for very large graphs composed by millions of nodes. In this paper we propose a solution that estimates the current flow betweenness in a distributed setting, by defining a vertex-centric, gossip-based algorithm. Each node, relying on its local information, in a self-adaptive way generates new flows to improve the betweenness of all the nodes of the graph. Our experimental evaluation shows that our proposal achieves high correlation with the exact current flow betweenness, and provides a good centrality measure for large graphs.
Source: 2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems, pp. 71–80, Boston, USA, 21-25/09/2015
[1] L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, pp. 35-41, 1977.
[2] L. Freeman, S. Borgatti, and D. White, “Centrality in valued graphs: A measure of betweenness based on network flow,” Social Networks, vol. 13, no. 2, 1991.
[3] M. Newman, “A measure of betweeness centrality based on random walks,” Social Networks, vol. 27, 2005.
[4] U. Brandes and D. Fleischer, “Centrality measures based on current flow,” in Lecture Notes in Computer Science, vol. 3404, 2005, pp. 533- 544.
[5] M. E. Newman, “A measure of betweenness centrality based on random walks,” Social networks, vol. 27, no. 1, pp. 39-54, 2005.
[6] E. Bozzo and M. Franceschet, “Approximations of the generalized inverse of the graph laplacian matrix,” Internet Mathematics, vol. 8, no. 4, pp. 456-481, 2012.
[7] K. Avrachenkov, N. Litvak, V. Medyanikov, and M. Sokol, “Alpha current flow betweenness centrality,” in Algorithms and Models for the Web Graph. Springer, 2013, pp. 106-117.
[8] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: cluster computing with working sets,” in Proceedings of the 2nd USENIX conference on Hot topics in cloud computing, 2010, pp. 10-10.
[9] K. Shvachko, H. Kuang, S. Radia, and R. Chansler, “The hadoop distributed file system,” in Mass Storage Systems and Technologies (MSST), 2010 IEEE 26th Symposium on. IEEE, 2010, pp. 1-10.
[10] U. Brandes, “A faster algorithm for betweenness centrality,” Journal of Mathematical Sociology, vol. 25, pp. 163-177, 2001.
[11] M. Riondato and E. M. Kornaropoulos, “Fast approximation of betweenness centrality through sampling,” in Proceedings of the 7th ACM Conference on Web Search and Data Mining, WSDM, vol. 14, 2013.
[12] W. Hoeffding, “Probabilty inequalities for sums of bounded random variales,” Journal of american Statistical Association, vol. 58, pp. 13- 30, 1963.
[13] E. Bozzo and M. Franceschet, “Resistance distance, closeness, and betweenness,” Social Networks, vol. 35, no. 3, pp. 460-469, 2013.
[14] K. A. Lehmann and M. Kaufmann, “Decentralized algorithms for evaluating centrality in complex networks,” Department of Computer Science, Michigan State University, Wilhelm-Schickard-Institut, Tech. Rep. WSI-2003-10, October 2003.
[15] K. Wehmuth and A. Ziviani, “DACCER: distributed assessment of the closeness centrality ranking in complex networks,” Computer Networks, vol. 57, no. 13, pp. 2536-2548, 2013.
[16] A. Kermarrec, E. L. Merrer, B. Sericola, and G. Tre´dan, “Second order centrality: Distributed assessment of nodes criticity in complex networks,” Computer Communications, vol. 34, no. 5, pp. 619-628, 2011.
[17] P. G. Doyle and J. L. Snell, “Random walks and electric networks,” 2006.
[18] R. Baraglia, P. Dazzi, M. Mordacchini, and L. Ricci, “A peer-to-peer recommender system for self-emerging user communities based on gossip overlays,” Journal of Computer and System Sciences, vol. 79, no. 2, pp. 291-308, 2013.
[19] R. Baraglia, P. Dazzi, M. Mordacchini, L. Ricci, and L. Alessi, “Group: A gossip based building community protocol,” in Smart Spaces and Next Generation Wired/Wireless Networking. Springer Berlin Heidelberg, 2011, pp. 496-507.
[20] P. Dazzi, P. Felber, L. Leonini, M. Mordacchini, R. Perego, M. Rajman, and E´. Rivie`re, “Peer-to-peer clustering of web-browsing users,” Proc. LSDS-IR, pp. 71-78, 2009.
[21] M. Mordacchini, P. Dazzi, G. Tolomei, R. Baraglia, F. Silvestri, and S. Orlando, “Challenges in designing an interest-based distributed aggregation of users in p2p systems,” in Ultra Modern Telecommunications & Workshops, 2009. ICUMT'09. International Conference on. IEEE, 2009, pp. 1-8.
[22] E. Carlini, M. Coppola, P. Dazzi, D. Laforenza, S. Martinelli, and L. Ricci, “Service and resource discovery supports over p2p overlays,” in Ultra Modern Telecommunications & Workshops, 2009. ICUMT'09. International Conference on. IEEE, 2009, pp. 1-8.
[23] R. Baraglia, P. Dazzi, B. Guidi, and L. Ricci, “Godel: Delaunay overlays in p2p networks via gossip,” in IEEE 12th International Conference on Peer-to-Peer Computing (P2P). IEEE, 2012, pp. 1-12.
[24] E. Carlini, L. Ricci, and M. Coppola, “Reducing server load in mmog via p2p gossip,” in Proceedings of the 11th Annual Workshop on Network and Systems Support for Games. IEEE Press, 2012, p. 11.
[25] E. Carlini, P. Dazzi, A. Esposito, A. Lulli, and L. Ricci, “Balanced graph partitioning with apache spark,” in Euro-Par 2014: Parallel Processing Workshops. Springer, 2014, pp. 129-140.
[26] M. Jelasity, S. Voulgaris, R. Guerraoui, A.-M. Kermarrec, and M. Van Steen, “Gossip-based peer sampling,” ACM Transactions on Computer Systems (TOCS), vol. 25, no. 3, p. 8, 2007.
[27] S. Voulgaris, D. Gavidia, and M. Van Steen, “Cyclon: Inexpensive membership management for unstructured p2p overlays,” Journal of Network and Systems Management, vol. 13, no. 2, pp. 197-217, 2005.
[28] L. Massoulie´, E. Le Merrer, A.-M. Kermarrec, and A. Ganesh, “Peer counting and sampling in overlay networks: random walk methods,” in Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing. ACM, 2006, pp. 123-132.
[29] M. Jelasity, A. Montresor, and O. Babaoglu, “Gossip-based aggregation in large dynamic networks,” ACM Transactions on Computer Systems (TOCS), vol. 23, no. 3, pp. 219-252, 2005.
[30] F. Rahimian, A. H. Payberah, S. Girdzijauskas, M. Jelasity, and S. Haridi, “Ja-be-ja: A distributed algorithm for balanced graph partitioning,” in Self-Adaptive and Self-Organizing Systems (SASO), 2013 IEEE 7th International Conference on. IEEE, 2013, pp. 51-60.
[31] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American statistical association, vol. 58, no. 301, pp. 13-30, 1963.
[32] A. Montresor and M. Jelasity, “Peersim: A scalable p2p simulator,” in Peer-to-Peer Computing, 2009, Ninth International Conference on. IEEE, 2009, pp. 99-100.
[33] J. Leskovec and R. Sosicˇ, “Snap.py: SNAP for Python, a general purpose network analysis and graph mining tool in Python,” http://snap.stanford. edu/snappy, Jun. 2014.
[34] D. Chakrabarti, Y. Zhan, and C. Faloutsos, “R-mat: A recursive model for graph mining.” in SDM, vol. 4. SIAM, 2004, pp. 442-446.
[35] D. A. Schult and P. Swart, “Exploring network structure, dynamics, and function using networkx,” in Proceedings of the 7th Python in Science Conferences (SciPy 2008), vol. 2008, 2008, pp. 11-16.
[36] U. Demsˇar, O. Sˇpatenkova´, and K. Virrantaus, “Identifying critical locations in a spatial network with graph theory,” Transactions in GIS, vol. 12, no. 1, pp. 61-82, 2008.
[37] U. Brandes and C. Pich, “Centrality estimation in large networks,” International Journal of Bifurcation and Chaos, vol. 17, no. 07, pp. 2303-2318, 2007.
[38] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014.
[39] A. Lulli, L. Ricci, E. Carlini, P. Dazzi, and C. Lucchese, “Cracker: Crumbling large graphs into connected components,” in 20th IEEE Symposium on Computers and Communication (ISCC) (ISCC2015), Larnaca, Cyprus, Jul. 2015.
[2] L. Freeman, S. Borgatti, and D. White, “Centrality in valued graphs: A measure of betweenness based on network flow,” Social Networks, vol. 13, no. 2, 1991.
[3] M. Newman, “A measure of betweeness centrality based on random walks,” Social Networks, vol. 27, 2005.
[4] U. Brandes and D. Fleischer, “Centrality measures based on current flow,” in Lecture Notes in Computer Science, vol. 3404, 2005, pp. 533- 544.
[5] M. E. Newman, “A measure of betweenness centrality based on random walks,” Social networks, vol. 27, no. 1, pp. 39-54, 2005.
[6] E. Bozzo and M. Franceschet, “Approximations of the generalized inverse of the graph laplacian matrix,” Internet Mathematics, vol. 8, no. 4, pp. 456-481, 2012.
[7] K. Avrachenkov, N. Litvak, V. Medyanikov, and M. Sokol, “Alpha current flow betweenness centrality,” in Algorithms and Models for the Web Graph. Springer, 2013, pp. 106-117.
[8] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: cluster computing with working sets,” in Proceedings of the 2nd USENIX conference on Hot topics in cloud computing, 2010, pp. 10-10.
[9] K. Shvachko, H. Kuang, S. Radia, and R. Chansler, “The hadoop distributed file system,” in Mass Storage Systems and Technologies (MSST), 2010 IEEE 26th Symposium on. IEEE, 2010, pp. 1-10.
[10] U. Brandes, “A faster algorithm for betweenness centrality,” Journal of Mathematical Sociology, vol. 25, pp. 163-177, 2001.
[11] M. Riondato and E. M. Kornaropoulos, “Fast approximation of betweenness centrality through sampling,” in Proceedings of the 7th ACM Conference on Web Search and Data Mining, WSDM, vol. 14, 2013.
[12] W. Hoeffding, “Probabilty inequalities for sums of bounded random variales,” Journal of american Statistical Association, vol. 58, pp. 13- 30, 1963.
[13] E. Bozzo and M. Franceschet, “Resistance distance, closeness, and betweenness,” Social Networks, vol. 35, no. 3, pp. 460-469, 2013.
[14] K. A. Lehmann and M. Kaufmann, “Decentralized algorithms for evaluating centrality in complex networks,” Department of Computer Science, Michigan State University, Wilhelm-Schickard-Institut, Tech. Rep. WSI-2003-10, October 2003.
[15] K. Wehmuth and A. Ziviani, “DACCER: distributed assessment of the closeness centrality ranking in complex networks,” Computer Networks, vol. 57, no. 13, pp. 2536-2548, 2013.
[16] A. Kermarrec, E. L. Merrer, B. Sericola, and G. Tre´dan, “Second order centrality: Distributed assessment of nodes criticity in complex networks,” Computer Communications, vol. 34, no. 5, pp. 619-628, 2011.
[17] P. G. Doyle and J. L. Snell, “Random walks and electric networks,” 2006.
[18] R. Baraglia, P. Dazzi, M. Mordacchini, and L. Ricci, “A peer-to-peer recommender system for self-emerging user communities based on gossip overlays,” Journal of Computer and System Sciences, vol. 79, no. 2, pp. 291-308, 2013.
[19] R. Baraglia, P. Dazzi, M. Mordacchini, L. Ricci, and L. Alessi, “Group: A gossip based building community protocol,” in Smart Spaces and Next Generation Wired/Wireless Networking. Springer Berlin Heidelberg, 2011, pp. 496-507.
[20] P. Dazzi, P. Felber, L. Leonini, M. Mordacchini, R. Perego, M. Rajman, and E´. Rivie`re, “Peer-to-peer clustering of web-browsing users,” Proc. LSDS-IR, pp. 71-78, 2009.
[21] M. Mordacchini, P. Dazzi, G. Tolomei, R. Baraglia, F. Silvestri, and S. Orlando, “Challenges in designing an interest-based distributed aggregation of users in p2p systems,” in Ultra Modern Telecommunications & Workshops, 2009. ICUMT'09. International Conference on. IEEE, 2009, pp. 1-8.
[22] E. Carlini, M. Coppola, P. Dazzi, D. Laforenza, S. Martinelli, and L. Ricci, “Service and resource discovery supports over p2p overlays,” in Ultra Modern Telecommunications & Workshops, 2009. ICUMT'09. International Conference on. IEEE, 2009, pp. 1-8.
[23] R. Baraglia, P. Dazzi, B. Guidi, and L. Ricci, “Godel: Delaunay overlays in p2p networks via gossip,” in IEEE 12th International Conference on Peer-to-Peer Computing (P2P). IEEE, 2012, pp. 1-12.
[24] E. Carlini, L. Ricci, and M. Coppola, “Reducing server load in mmog via p2p gossip,” in Proceedings of the 11th Annual Workshop on Network and Systems Support for Games. IEEE Press, 2012, p. 11.
[25] E. Carlini, P. Dazzi, A. Esposito, A. Lulli, and L. Ricci, “Balanced graph partitioning with apache spark,” in Euro-Par 2014: Parallel Processing Workshops. Springer, 2014, pp. 129-140.
[26] M. Jelasity, S. Voulgaris, R. Guerraoui, A.-M. Kermarrec, and M. Van Steen, “Gossip-based peer sampling,” ACM Transactions on Computer Systems (TOCS), vol. 25, no. 3, p. 8, 2007.
[27] S. Voulgaris, D. Gavidia, and M. Van Steen, “Cyclon: Inexpensive membership management for unstructured p2p overlays,” Journal of Network and Systems Management, vol. 13, no. 2, pp. 197-217, 2005.
[28] L. Massoulie´, E. Le Merrer, A.-M. Kermarrec, and A. Ganesh, “Peer counting and sampling in overlay networks: random walk methods,” in Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing. ACM, 2006, pp. 123-132.
[29] M. Jelasity, A. Montresor, and O. Babaoglu, “Gossip-based aggregation in large dynamic networks,” ACM Transactions on Computer Systems (TOCS), vol. 23, no. 3, pp. 219-252, 2005.
[30] F. Rahimian, A. H. Payberah, S. Girdzijauskas, M. Jelasity, and S. Haridi, “Ja-be-ja: A distributed algorithm for balanced graph partitioning,” in Self-Adaptive and Self-Organizing Systems (SASO), 2013 IEEE 7th International Conference on. IEEE, 2013, pp. 51-60.
[31] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American statistical association, vol. 58, no. 301, pp. 13-30, 1963.
[32] A. Montresor and M. Jelasity, “Peersim: A scalable p2p simulator,” in Peer-to-Peer Computing, 2009, Ninth International Conference on. IEEE, 2009, pp. 99-100.
[33] J. Leskovec and R. Sosicˇ, “Snap.py: SNAP for Python, a general purpose network analysis and graph mining tool in Python,” http://snap.stanford. edu/snappy, Jun. 2014.
[34] D. Chakrabarti, Y. Zhan, and C. Faloutsos, “R-mat: A recursive model for graph mining.” in SDM, vol. 4. SIAM, 2004, pp. 442-446.
[35] D. A. Schult and P. Swart, “Exploring network structure, dynamics, and function using networkx,” in Proceedings of the 7th Python in Science Conferences (SciPy 2008), vol. 2008, 2008, pp. 11-16.
[36] U. Demsˇar, O. Sˇpatenkova´, and K. Virrantaus, “Identifying critical locations in a spatial network with graph theory,” Transactions in GIS, vol. 12, no. 1, pp. 61-82, 2008.
[37] U. Brandes and C. Pich, “Centrality estimation in large networks,” International Journal of Bifurcation and Chaos, vol. 17, no. 07, pp. 2303-2318, 2007.
[38] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014.
[39] A. Lulli, L. Ricci, E. Carlini, P. Dazzi, and C. Lucchese, “Cracker: Crumbling large graphs into connected components,” in 20th IEEE Symposium on Computers and Communication (ISCC) (ISCC2015), Larnaca, Cyprus, Jul. 2015.
Metrics
Back to previous page
BibTeX entry
@inproceedings{oai:it.cnr:prodotti:344345,
title = {Distributed Current Flow Betweenness Centrality},
author = {Lulli A. and Ricci L. and Carlini E. Dazzi P.},
doi = {10.1109/saso.2015.15},
booktitle = {2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems, pp. 71–80, Boston, USA, 21-25/09/2015},
year = {2015}
}
0000-0003-3643-5404