Local dependency in networks

Miloš Kudělka ; Šárka Zehnalová ; Zdeněk Horák ; Pavel Krömer ; Václav Snášel

International Journal of Applied Mathematics and Computer Science, Tome 25 (2015), p. 281-293 / Harvested from The Polish Digital Mathematics Library

Résumé

Many real world data and processes have a network structure and can usefully be represented as graphs. Network analysis focuses on the relations among the nodes exploring the properties of each network. We introduce a method for measuring the strength of the relationship between two nodes of a network and for their ranking. This method is applicable to all kinds of networks, including directed and weighted networks. The approach extracts dependency relations among the network's nodes from the structure in local surroundings of individual nodes. For the tasks we deal with in this article, the key technical parameter is locality. Since only the surroundings of the examined nodes are used in computations, there is no need to analyze the entire network. This allows the application of our approach in the area of large-scale networks. We present several experiments using small networks as well as large-scale artificial and real world networks. The results of the experiments show high effectiveness due to the locality of our approach and also high quality node ranking comparable to PageRank.

Détail

Publié le : 2015-01-01

Zbl 1322.94130

EUDML-ID : urn:eudml:doc:270781

Bibliographie

[000] Abdallah, S. (2011). Generalizing unweighted network measures to capture the focus in interactions, Social Network Analysis and Mining 1(4): 255-269.

[001] Bar-Yossef, Z. and Mashiach, L.-T. (2008). Local approximation of PageRank and reverse PageRank, Proceedings of the 17th ACM Conference on Information and Knowledge Management, Napa Valley, CA, USA, pp. 279-288.

[002] Barabási, A.-L. and Frangos, J. (2002). Linked: The New Science of Networks Science Of Networks, Basic Books, New York, NY.

[003] Barrat, A., Barthelemy, M., Pastor-Satorras, R. and Vespignani, A. (2004a). The architecture of complex weighted networks, Proceedings of the National Academy of Sciences of the United States of America 101(11): 3747-3752.

[004] Barrat, A., Barthélemy, M. and Vespignani, A. (2004b). Weighted evolving networks: coupling topology and weight dynamics, Physical Review Letters 92(22): 228701.

[005] Brin, S. and Page, L. (1998). The anatomy of a large-scale hypertextual web search engine, Proceedings of the 7th International Conference on World Wide Web, Brisbane, Australia, pp. 107-117.

[006] Christensen, D. (2005). Fast algorithms for the calculation of Kendall τ , Computational Statistics 20(1): 51-62. | Zbl 1089.62067

[007] Das Sarma, A., Molla, A., Pandurangan, G. and Upfal, E. (2013). Fast distributed PageRank computation, in D. Frey, M. Raynal, S. Sarkar, R. Shyamasundar and P. Sinha (Eds.), Distributed Computing and Networking, Lecture Notes in Computer Science, Vol. 7730, Springer, Berlin/Heidelberg, pp. 11-26. | Zbl 1303.68148

[008] de Jager, D. (2004). PageRank: Three Distributed Algorithms, Master's thesis, Imperial College London, London, pubs.doc.ic.ac.uk/pagerank-algorithms/.

[009] Farkas, I., Ábel, D., Palla, G. and Vicsek, T. (2007). Weighted network modules, New Journal of Physics 9(6): 180.

[010] Fortunato, S. (2010). Community detection in graphs, Physics Reports 486(3): 75-174.

[011] Fortunato, S., Boguñá, M., Flammini, A. and Menczer, F. (2008). Approximating PageRank from in-degree, in W. Aiello, A. Broder, J. Janssen and E. Milios (Eds.), Algorithms and Models for the Web-Graph, Springer, Berlin/Heidelberg pp. 59-71. | Zbl 1142.68311

[012] Freeman, L.C. (1979). Centrality in social networks conceptual clarification, Social Networks 1(3): 215-239.

[013] Ghazalpour, A., Doss, S., Zhang, B., Wang, S., Plaisier, C., Castellanos, R., Brozell, A., Schadt, E.E., Drake, T.A., Lusis, A.J. and Horvath, S. (2006). Integrating genetic and network analysis to characterize genes related to mouse weight, PLoS Genetics 2(8): e130.

[014] Han, Y., Zhou, B., Pei, J. and Jia, Y. (2009). Understanding importance of collaborations in co-authorship networks: A supportiveness analysis approach, Proceedings of the 9th SIAM International Conference on Data Mining, Sparks, NV, USA, pp. 1111-1122.

[015] Heckerman, D., Chickering, D. M., Meek, C., Rounthwaite, R. and Kadie, C. (2001). Dependency networks for inference, collaborative filtering, and data visualization, The Journal of Machine Learning Research 1: 49-75. | Zbl 1008.68132

[016] Kahanda, I. and Neville, J. (2009). Using transactional information to predict link strength in online social networks, Proceedings of the 3rd International Conference on Weblogs and Social Media (ICWSM), San Jose, CA, USA, pp. 74-81.

[017] Kenett, D.Y., Tumminello, M., Madi, A., Gur-Gershgoren, G., Mantegna, R.N. and Ben-Jacob, E. (2010). Dominating clasp of the financial sector revealed by partial correlation analysis of the stock market, PLoS One 5(12): e15032.

[018] Kudělka, M., Horák, Z., Snášel, V., Krömer, P., Platoš, J. and Abraham, A. (2012). Social and swarm aspects of co-authorship network, Logic Journal of IGPL 20(3): 634-643.

[019] Langville, A.N. and Meyer, C.D. (2006). Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, NJ. | Zbl 1104.68042

[020] Leenders, R.T.A. (2002). Modeling social influence through network autocorrelation: Constructing the weight matrix, Social Networks 24(1): 21-47.

[021] Lin, J. and Dyer, C. (2010). Data-intensive Text Processing with MapReduce, Synthesis Lectures on Human Language Technologies, Morgan & Claypool, San Rafael, CA.

[022] Lusseau, D. (2003). The emergent properties of a dolphin social network, Proceedings of the Royal Society of London, Series B: Biological Sciences 270(Suppl 2): S186-S188.

[023] Manaskasemsak, B. and Rungsawang, A. (2004). Parallel PageRank computation on a gigabit PC cluster, 18th International Conference on Advanced Information Networking and Applications, AINA 2004, Fukuoka, Japan, Vol. 1, pp. 273-277.

[024] Manaskasemsak, B., Uthayopas, P. and Rungsawang, A. (2006). A mixed MPI-thread approach for parallel page ranking computation, in R. Meersman and Z. Tari (Eds.), Proceedings of the 2006 Confederated International Conference on On the Move to Meaningful Internet Systems: CoopIS, DOA, GADA, and ODBASE, Part II, Springer-Verlag, Berlin/Heidelberg, pp. 1223-1233.

[025] Newman, M. (2008). The physics of networks, Physics Today 61(11): 33-38.

[026] Newman, M.E. (2004). Analysis of weighted networks, Physical Review E 70(5): 056131.

[027] Newman, M.E. (2006). Finding community structure in networks using the eigenvectors of matrices, Physical Review E 74(3): 036104.

[028] Nitzberg, B., Schopf, J. and Jones, J. (2004). PBS Pro: Grid computing and scheduling attributes, in J. Nabrzyski, J. Schopf and J. W˛eglarz (Eds.), Grid Resource Management, International Series in Operations Research and Management Science, Vol. 64, Springer, New York, NY, pp. 183-190.

[029] Onnela, J.-P., Saramäki, J., Hyvönen, J., Szabó, G., De Menezes, M. A., Kaski, K., Barabási, A.-L. and Kertész, J. (2007). Analysis of a large-scale weighted network of one-to-one human communication, New Journal of Physics 9(6): 179.

[030] Opsahl, T., Agneessens, F. and Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths, Social Networks 32(3): 245-251.

[031] Opsahl, T. and Panzarasa, P. (2009). Clustering in weighted networks, Social Networks 31(2): 155-163.

[032] Plimpton, S.J. and Devine, K.D. (2011). MapReduce in MPI for large-scale graph algorithms, Parallel Computing 37(9): 610-632.

[033] Rungsawang, A. and Manaskasemsak, B. (2003). PageRank computation using PC cluster, in J. Dongarra, D. Laforenza and S. Orlando (Eds.), Recent Advances in Parallel Virtual Machine and Message Passing Interface, Lecture Notes in Computer Science, Vol. 2840, Springer Berlin/Heidelberg, pp. 152-159.

[034] Sankaralingam, K., Sethumadhavan, S. and Browne, J. (2003). Distributed PageRank for P2P systems, 12th IEEE International Symposium on High Performance Distributed Computing, 2003, Seattle, WA, USA, pp. 58-68.

[035] Wiedermann, M., Donges, J.F., Heitzig, J. and Kurths, J. (2013). Node-weighted interacting network measures improve the representation of real-world complex systems, Europhysics Letters 102(2): 28007.

[036] Witten, I.H., Gori, M. and Numerico, T. (2006). Web Dragons: Inside the Myths of Search Engine Technology, Morgan Kaufmann, San Francisco, CA.

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

[038] Zehnalova, S., Horak, Z., Kudelka, M. and Snael, V. (2013). Local dependency in networks, 5th International Conference on Intelligent Networking and Collaborative Systems (INCoS), Xi'an, China, pp. 250-254.

[039] Zhang, B. and Horvath, S. (2005). A general framework for weighted gene co-expression network analysis, Statistical Applications in Genetics and Molecular Biology 4(1): 1128. | Zbl 1077.92042

[040] Zhu, Y., Ye, S. and Li, X. (2005). Distributed PageRank computation based on iterative aggregation-disaggregation methods, Proceedings of the 14th ACM International Conference on Information and Knowledge Management, CIKM'05, Bremen, Germany, pp. 578-585.