Local dependency in networks

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

doi:10.1515/amcs-2015-0022

Abstract

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.

References

Abdallah, S. (2011). Generalizing unweighted network measures to capture the focus in interactions, Social Network Analysis and Mining 1(4): 255-269.10.1007/s13278-011-0018-8
Search in Google Scholar
Bar-Yossef, Z. andMashiach, 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.
Search in Google Scholar
Barabási, A.-L. and Frangos, J. (2002). Linked: The New Science of Networks Science Of Networks, Basic Books, New York, NY.
Search in Google Scholar
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.10.1073/pnas.0400087101
Search in Google Scholar
Barrat, A., Barthélemy, M. and Vespignani, A. (2004b). Weighted evolving networks: coupling topology and weight dynamics, Physical Review Letters 92(22): 228701. 10.1103/PhysRevLett.92.228701
Search in Google Scholar
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.
Search in Google Scholar
Christensen, D. (2005). Fast algorithms for the calculation of Kendall τ , Computational Statistics 20(1): 51-62.10.1007/BF02736122
Search in Google Scholar
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.
Search in Google Scholar
de Jager, D. (2004). PageRank: Three Distributed Algorithms, Master’s thesis, Imperial College London, London, pubs.doc.ic.ac.uk/pagerank-algorithms/.
Search in Google Scholar
Farkas, I., Ábel, D., Palla, G. and Vicsek, T. (2007). Weighted network modules, New Journal of Physics 9(6): 180.10.1088/1367-2630/9/6/180
Search in Google Scholar
Fortunato, S. (2010). Community detection in graphs, Physics Reports 486(3): 75-174.10.1016/j.physrep.2009.11.002
Search in Google Scholar
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.10.1007/978-3-540-78808-9_6
Search in Google Scholar
Freeman, L.C. (1979). Centrality in social networks conceptual clarification, Social Networks 1(3): 215-239.10.1016/0378-8733(78)90021-7
Search in Google Scholar
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.10.1371/journal.pgen.0020130155028316934000
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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. 10.1371/journal.pone.0015032300479221188140
Search in Google Scholar
Kudelka, 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.10.1093/jigpal/jzr002
Search in Google Scholar
Langville, A.N. and Meyer, C.D. (2006). Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, NJ.10.1515/9781400830329
Search in Google Scholar
Leenders, R.T.A. (2002). Modeling social influence through network autocorrelation: Constructing the weight matrix, Social Networks 24(1): 21-47.10.1016/S0378-8733(01)00049-1
Search in Google Scholar
Lin, J. and Dyer, C. (2010). Data-intensive Text Processing with MapReduce, Synthesis Lectures on Human Language Technologies, Morgan & Claypool, San Rafael, CA.10.2200/S00274ED1V01Y201006HLT007
Search in Google Scholar
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.10.1098/rsbl.2003.0057180995414667378
Search in Google Scholar
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.
Search in Google Scholar
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.10.1007/11914952_12
Search in Google Scholar
Newman, M. (2008). The physics of networks, Physics Today 61(11): 33-38.10.1063/1.3027989
Search in Google Scholar
Newman, M.E. (2004). Analysis of weighted networks, Physical Review E 70(5): 056131.10.1103/PhysRevE.70.05613115600716
Search in Google Scholar
Newman, M.E. (2006). Finding community structure in networks using the eigenvectors of matrices, Physical Review E 74(3): 036104.10.1103/PhysRevE.74.03610417025705
Search in Google Scholar
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.10.1007/978-1-4615-0509-9_13
Search in Google Scholar
Onnela, J.-P., Saramäki, J., Hyvönen, J., Szabó, G., DeMenezes, 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.10.1088/1367-2630/9/6/179
Search in Google Scholar
Opsahl, T., Agneessens, F. and Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths, Social Networks 32(3): 245-251.10.1016/j.socnet.2010.03.006
Search in Google Scholar
Opsahl, T. and Panzarasa, P. (2009). Clustering in weighted networks, Social Networks 31(2): 155-163.10.1016/j.socnet.2009.02.002
Search in Google Scholar
Plimpton, S.J. and Devine, K.D. (2011). MapReduce in MPI for large-scale graph algorithms, Parallel Computing 37(9): 610-632.10.1016/j.parco.2011.02.004
Search in Google Scholar
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.10.1007/978-3-540-39924-7_24
Search in Google Scholar
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.
Search in Google Scholar
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.10.1209/0295-5075/102/28007
Search in Google Scholar
Witten, I.H., Gori, M. and Numerico, T. (2006). Web Dragons: Inside the Myths of Search Engine Technology, Morgan Kaufmann, San Francisco, CA. Zachary, W.W. (1977). An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33(4): 452-473.
Search in Google Scholar
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.
Search in Google Scholar
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.10.2202/1544-6115.112816646834
Search in Google Scholar
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.
Search in Google Scholar

Local dependency in networks

Abstract

Paradigm

My account