Weighted Linking Decomposition: Mining Denser and More Compact Hierarchies for Bipartite Graphs
DOI:
https://doi.org/10.5753/jidm.2020.2031Keywords:
bipartite graphs, dense subgraphs, graph mining, hierarchical decompositionAbstract
Dense subgraph detection is a well-known problem in graph theory. The hierarchical organization of graphs as dense subgraphs, however, goes beyond simple clustering, as it allows the analysis of the network at different scales.
Although there are several hierarchical decomposition methods for unipartite graphs, only a few approaches for the bipartite case have been proposed. In this work, we explore the problem of hierarchical decomposition for bipartite graphs.
We propose an algorithm called Weighted Linking that identifies denser and more compact hierarchies than the state of the art approach. We also propose a new score to help choose the best between two hierarchical decompositions of the same graph.
The proposed algorithm was evaluated experimentally using six real-world datasets and identified smaller and denser hierarchies on most of them.
Downloads
References
Abello, J. and Korn, J. Mgv: A system for visualizing massive multidigraphs. IEEE Transactions on Visualization and Computer Graphics 8 (1): 21–38, 2002.
Al-garadi, M. A., Varathan, K. D., and Ravana, S. D. Identification of influential spreaders in online social networks using interaction weighted k-core decomposition method. Physica A: Statistical Mechanics and its Applications vol. 468, pp. 278–288, 2017.
Alberich, R., Miro-Julia, J., and Rossello, F. Marvel universe looks almost like a real social network, 2002. cite arxiv:condmat/0202174Comment: 14 pages, 3 figures.
Alvarez-hamelin, J. I., asta, L. D., Barrat, A., and Vespignani, A. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems 18, Y. Weiss, B. Schölkopf, and J. C. Platt (Eds.). MIT Press, pp. 41–50, 2006.
Andersen, R. and Chellapilla, K. Finding dense subgraphs with size bounds. In Algorithms and Models for the Web-Graph, K. Avrachenkov, D. Donato, and N. Litvak (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 25–37, 2009.
Asahiro, Y., Iwama, K., Tamaki, H., and Tokuyama, T. Greedily finding a dense subgraph. Journal of Algorithms 34 (2): 203–221, 2000.
Ban, Y. On finding dense subgraphs in bipartite graphs: Linear algorithms with applications to fraud detection, 2018.
Batagelj, V. and Zaversnik, M. Generalized cores. CoRR vol. cs.DS/0202039, 2002.
Bonchi, F., Gullo, F., Kaltenbrunner, A., and Volkovich, Y. Core decomposition of uncertain graphs. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’14. ACM, New York, NY, USA, pp. 1316–1325, 2014.
Brown, P. E. and Feng, J. Measuring user influence on twitter using modified k-shell decomposition. In Fifth international AAAI conference on weblogs and social media, 2011.
Charikar, M. Greedy approximation algorithms for finding dense components in a graph. In Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization. APPROX ’00. Springer-Verlag, Berlin, Heidelberg, pp. 84–95, 2000.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C., et al. Introduction to algorithms, 2001.
Galimberti, E., Bonchi, F., and Gullo, F. Core decomposition and densest subgraph in multilayer networks. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. ACM, pp. 1807–1816, 2017.
Giatsidis, C., Thilikos, D. M., and Vazirgiannis, M. Evaluating cooperation in communities with the k-core structure. In 2011 International Conference on Advances in Social Networks Analysis and Mining. pp. 87–93, 2011.
Giatsidis, C., Thilikos, D. M., and Vazirgiannis, M. D-cores: measuring collaboration of directed graphs based on degeneracy. Knowledge and information systems 35 (2): 311–343, 2013.
Goldberg, A. V. Finding a maximum density subgraph. Tech. rep., Berkeley, CA, USA, 1984.
Khuller, S. and Saha, B. On finding dense subgraphs. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I. ICALP ’09. Springer-Verlag, Berlin, Heidelberg, pp. 597–608, 2009.
Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., and Makse, H. A. Identification of influential spreaders in complex networks. Nature physics 6 (11): 888, 2010.
Kunegis, J. Konect: The koblenz network collection. In Proceedings of the 22Nd International Conference on World Wide Web. WWW ’13 Companion. ACM, New York, NY, USA, pp. 1343–1350, 2013.
Lee, V. E., Ruan, N., Jin, R., and Aggarwal, C. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data. Springer, pp. 303–336, 2010.
Malliaros, F. D., Giatsidis, C., Papadopoulos, A. N., and Vazirgiannis, M. The core decomposition of networks: theory, algorithms and applications. The VLDB Journal, 2019.
Moreira, E., Campos, G. O., and Meira Jr, W. Dense hierarchy decomposition for bipartite graphs. In Anais do VII Symposium on Knowledge Discovery, Mining and Learning. SBC, pp. 105–112, 2019.
Sarıyüce, A. E., Gedik, B., Jacques-Silva, G., Wu, K.-L., and Çatalyürek, Ü. V. Incremental k-core decomposition: algorithms and evaluation. The VLDB Journal—The International Journal on Very Large Data Bases 25 (3): 425–447, 2016.
Sariyüce, A. E. and Pinar, A. Fast hierarchy construction for dense subgraphs. Proceedings of the VLDB Endowment 10 (3): 97–108, 2016.
Sariyüce, A. E. and Pinar, A. Peeling bipartite networks for dense subgraph discovery. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. WSDM ’18. ACM, New York, NY, USA, pp. 504–512, 2018.
Seidman, S. B. Network structure and minimum degree. Social networks 5 (3): 269–287, 1983.
Shin, K., Eliassi-Rad, T., and Faloutsos, C. Corescope: Graph mining using k-core analysis — patterns, anomalies and algorithms. In 2016 IEEE 16th International Conference on Data Mining (ICDM). pp. 469–478, 2016.
Tsourakakis, C., Bonchi, F., Gionis, A., Gullo, F., and Tsiarli, M. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’13. ACM, New York, NY, USA, pp. 104–112, 2013.
Wu, H., Cheng, J., Lu, Y., Ke, Y., Huang, Y., Yan, D., and Wu, H. Core decomposition in large temporal graphs. In 2015 IEEE International Conference on Big Data (Big Data). pp. 649–658, 2015.
Zitnik, M., Sosič, R., Maheshwari, S., and Leskovec, J. BioSNAP Datasets: Stanford biomedical network dataset collection. http://snap.stanford.edu/biodata, 2018.
