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 (2015)

  • Volume: 25, Issue: 2, page 281-293
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Miloš Kudělka, et al. "Local dependency in networks." International Journal of Applied Mathematics and Computer Science 25.2 (2015): 281-293. <http://eudml.org/doc/270781>.

@article{MilošKudělka2015,
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.},
author = {Miloš Kudělka, Šárka Zehnalová, Zdeněk Horák, Pavel Krömer, Václav Snášel},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {complex networks; graphs; edge weighting; dependency},
language = {eng},
number = {2},
pages = {281-293},
title = {Local dependency in networks},
url = {http://eudml.org/doc/270781},
volume = {25},
year = {2015},
}

TY - JOUR
AU - Miloš Kudělka
AU - Šárka Zehnalová
AU - Zdeněk Horák
AU - Pavel Krömer
AU - Václav Snášel
TI - Local dependency in networks
JO - International Journal of Applied Mathematics and Computer Science
PY - 2015
VL - 25
IS - 2
SP - 281
EP - 293
AB - 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.
LA - eng
KW - complex networks; graphs; edge weighting; dependency
UR - http://eudml.org/doc/270781
ER -

References

top
  1. Abdallah, S. (2011). Generalizing unweighted network measures to capture the focus in interactions, Social Network Analysis and Mining 1(4): 255-269. 
  2. 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. 
  3. Barabási, A.-L. and Frangos, J. (2002). Linked: The New Science of Networks Science Of Networks, Basic Books, New York, NY. 
  4. 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. 
  5. Barrat, A., Barthélemy, M. and Vespignani, A. (2004b). Weighted evolving networks: coupling topology and weight dynamics, Physical Review Letters 92(22): 228701. 
  6. 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. 
  7. Christensen, D. (2005). Fast algorithms for the calculation of Kendall τ , Computational Statistics 20(1): 51-62. Zbl1089.62067
  8. 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. Zbl1303.68148
  9. de Jager, D. (2004). PageRank: Three Distributed Algorithms, Master's thesis, Imperial College London, London, pubs.doc.ic.ac.uk/pagerank-algorithms/. 
  10. Farkas, I., Ábel, D., Palla, G. and Vicsek, T. (2007). Weighted network modules, New Journal of Physics 9(6): 180. 
  11. Fortunato, S. (2010). Community detection in graphs, Physics Reports 486(3): 75-174. 
  12. 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. Zbl1142.68311
  13. Freeman, L.C. (1979). Centrality in social networks conceptual clarification, Social Networks 1(3): 215-239. 
  14. 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. 
  15. 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. 
  16. 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. Zbl1008.68132
  17. 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. 
  18. 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. 
  19. 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. 
  20. Langville, A.N. and Meyer, C.D. (2006). Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, NJ. Zbl1104.68042
  21. Leenders, R.T.A. (2002). Modeling social influence through network autocorrelation: Constructing the weight matrix, Social Networks 24(1): 21-47. 
  22. Lin, J. and Dyer, C. (2010). Data-intensive Text Processing with MapReduce, Synthesis Lectures on Human Language Technologies, Morgan & Claypool, San Rafael, CA. 
  23. 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. 
  24. 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. 
  25. 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. 
  26. Newman, M. (2008). The physics of networks, Physics Today 61(11): 33-38. 
  27. Newman, M.E. (2004). Analysis of weighted networks, Physical Review E 70(5): 056131. 
  28. Newman, M.E. (2006). Finding community structure in networks using the eigenvectors of matrices, Physical Review E 74(3): 036104. 
  29. 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. 
  30. 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. 
  31. Opsahl, T., Agneessens, F. and Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths, Social Networks 32(3): 245-251. 
  32. Opsahl, T. and Panzarasa, P. (2009). Clustering in weighted networks, Social Networks 31(2): 155-163. 
  33. Plimpton, S.J. and Devine, K.D. (2011). MapReduce in MPI for large-scale graph algorithms, Parallel Computing 37(9): 610-632. 
  34. 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. 
  35. 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. 
  36. 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. 
  37. Witten, I.H., Gori, M. and Numerico, T. (2006). Web Dragons: Inside the Myths of Search Engine Technology, Morgan Kaufmann, San Francisco, CA. 
  38. Zachary, W.W. (1977). An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33(4): 452-473. 
  39. 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. 
  40. 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. Zbl1077.92042
  41. 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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.