Dense Hierarchy Decomposition for Bipartite Graphs
Resumo
Dense subgraphs detection is a well known problem in Computer Science. Hierarchical organization of graphs as dense subgraphs, however, goes beyond simple clustering as it allows the analysis of the network at different scales. Despite the fact there are several works on hierarchical decomposition for unipartite graphs, only a few works for the bipartite case have been proposed. In this work we explore the problem of hierarchical decomposition of bipartite graphs. We propose an algorithm which we call weighted linking that produces denser and more compact hierarchies. The proposed algorithm is evaluated experimentally using several datasets and provided gains on most of them.
Palavras-chave:
bipartite graphs, dense subgraphs, graph mining, hierarchical decomposition
Referências
Abello, J. and Korn, J. Mgv: A system for visualizing massive multidigraphs. IEEE Transactions on Visualization and Computer Graphics 8 (1): 21–38, 2002.
Alberich, R., Miro-Julia, J., and Rossello, F. Marvel universe looks almost like a real social network, 2002. cite arxiv:condmat/0202174 Comment: 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.
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.
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.
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.
Saryuce, A. E., Gedik, B., Jacques-Silva, G., Wu, K.-L., and Çatalyurek, Ü. V. Incremental k-core decomposition: algorithms and evaluation. The VLDB Journal—The International Journal on Very Large Data Bases 25 (3): 425–447, 2016.
Sariyuce, A. E. and Pinar, A. Fast hierarchy construction for dense subgraphs. Proceedings of the VLDB Endowment 10 (3): 97–108, 2016.
Sariyuce, 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 quasicliques 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.
Alberich, R., Miro-Julia, J., and Rossello, F. Marvel universe looks almost like a real social network, 2002. cite arxiv:condmat/0202174 Comment: 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.
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.
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.
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.
Saryuce, A. E., Gedik, B., Jacques-Silva, G., Wu, K.-L., and Çatalyurek, Ü. V. Incremental k-core decomposition: algorithms and evaluation. The VLDB Journal—The International Journal on Very Large Data Bases 25 (3): 425–447, 2016.
Sariyuce, A. E. and Pinar, A. Fast hierarchy construction for dense subgraphs. Proceedings of the VLDB Endowment 10 (3): 97–108, 2016.
Sariyuce, 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 quasicliques 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.
Publicado
07/10/2019
Como Citar
MOREIRA, Edré; CAMPOS, Guilherme Oliveira; MEIRA JR., Wagner.
Dense Hierarchy Decomposition for Bipartite Graphs. In: SYMPOSIUM ON KNOWLEDGE DISCOVERY, MINING AND LEARNING (KDMILE) , 2019, Fortaleza.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 105-112.
ISSN 2763-8944.
DOI: https://doi.org/10.5753/kdmile.2019.8795.
