Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2022 | OriginalPaper | Buchkapitel

3. CSS on Bipartite Networks

verfasst von : Yixiang Fang, Kai Wang, Xuemin Lin, Wenjie Zhang

Erschienen in: Cohesive Subgraph Search Over Large Heterogeneous Information Networks

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In many real-world applications, relationships between two different types of entities (e.g., user-item people-location and author-paper) are naturally modeled as bipartite networks. When analyzing bipartite networks, CSMs and CSS techniques play an important role in many aspects including network measurement, dense region discovering, and network reinforcement. To meet the high demands in the era of big data, novel CSMs and CSS solutions over bipartite networks have been proposed recently. In this chapter, we extensively review existing studies of CSS over bipartite networks in the literature. Specifically, we discuss the core-, truss-, clique-, connectivity-, and density-based models and the solutions to search subgraphs following these models over bipartite networks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Preliminaries
Nächstes Kapitel CSS on Other General HINs
Literatur
1.
Abello, J., Resende, M. G., & Sudarsky, S. (2002). Massive quasi-clique detection. In Latin American symposium on theoretical informatics (pp. 598–612). Springer.
2.
Abidi, A., Chen, L., Zhou, R., & Liu, C. (2021). Searching personalized k-wing in large and dynamic bipartite graphs. arXiv preprint arXiv:2101.00810.
3.
Abidi, A., Zhou, R., Chen, L., & Liu, C. (2020). Pivot-based maximal biclique enumeration. In IJCAI (pp. 3558–3564).
4.
Acuña, V., Ferreira, C. E., Freire, A. S., & Moreno, E. (2014). Solving the maximum edge biclique packing problem on unbalanced bipartite graphs. Discrete Applied Mathematics, 164, 2–12.MathSciNetCrossRef
5.
Ahmed, A., Batagelj, V., Fu, X., Hong, S.-H., Merrick, D., & Mrvar, A. (2007). Visualisation and analysis of the internet movie database. In 2007 6th International Asia-Pacific Symposium on Visualization (pp. 17–24). IEEE.
6.
Ahuja, R. K., Orlin, J. B., Stein, C., & Tarjan, R. E. (1994). Improved algorithms for bipartite network flow. SIAM Journal on Computing, 23(5), 906–933.MathSciNetCrossRef
8.
Al-Yamani, A. A., Ramsundar, S., & Pradhan, D. K. (2007). A defect tolerance scheme for nanotechnology circuits. IEEE Transactions on Circuits and Systems I: Regular Papers, 54(11), 2402–2409.MathSciNetCrossRef
9.
Andersen, R. (2010). A local algorithm for finding dense subgraphs. ACM Transactions on Algorithms, 6(4), 1–12.MathSciNetCrossRef
11.
Ban, Y., & Duan, Y. (2018). On finding dense subgraphs in bipartite graphs: Linear algorithms. arXiv preprint arXiv:1810.06809.
15.
Batagelj, V., & Zaveršnik, M. (2011). Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 5(2), 129–145.MathSciNetCrossRef
23.
Cerinšek, M., & Batagelj, V. (2015). Generalized two-mode cores. Social Networks, 42, 80–87.CrossRef
29.
Chen, C., Zhu, Q., Wu, Y., Sun, R., Wang, X., & Liu, X. (2021). Efficient critical relationships identification in bipartite networks. In World Wide Web (pp. 1–21).
30.
Chen, H., & Liu, T. (2017). Maximum edge bicliques in tree convex bipartite graphs. In International Workshop on Frontiers in Algorithmics (pp. 47–55). Springer.
33.
Chen, L., Liu, C., Zhou, R., Xu, J., & Li, J. (2021). Efficient exact algorithms for maximum balanced biclique search in bipartite graphs (pp. 248–260).
36.
Chen, X., Wang, K., Lin, X., Zhang, W., Qin, L., & Zhang, Y. (2021). Efficiently answering reachability and path queries on temporal bipartite graphs. Proceedings of the VLDB Endowment, 14(10), 1845–1858.CrossRef
44.
Das, A., & Tirthapura, S. (2018). Incremental maintenance of maximal bicliques in a dynamic bipartite graph. IEEE Transactions on Multi-Scale Computing Systems, 4(3), 231–242.CrossRef
45.
Das, A., & Tirthapura, S. (2019). Shared-memory parallel maximal biclique enumeration. In HiPC (pp. 34–43).
47.
Dawande, M., Keskinocak, P., Swaminathan, J. M., & Tayur, S. (2001). On bipartite and multipartite clique problems. Journal of Algorithms, 41(2), 388–403.MathSciNetCrossRef
48.
Ding, D., Li, H., Huang, Z., & Mamoulis, N. (2017). Efficient fault-tolerant group recommendation using alpha-beta-core. In CIKM (pp. 2047–2050).
52.
Eppstein, D. (1994). Arboricity and bipartite subgraph listing algorithms. Information Processing Letters, 51(4), 207–211.MathSciNetCrossRef
68.
Giatsidis, C., Thilikos, D. M., & Vazirgiannis, M. (2011). Evaluating cooperation in communities with the k-core structure. In ASONAM (pp. 87–93). IEEE.
72.
Glover, F. (1997). Tabu search and adaptive memory programmin—advances, applications and challenges. In Interfaces in computer science and operations research (pp. 1–75). Springer.
77.
Hao, Y., Zhang, M., Wang, X., & Chen, C. (2020). Cohesive subgraph detection in large bipartite networks. In International Conference on Scientific and Statistical Database Management (pp. 1–4).
78.
Hartmanis, J. (1982). Computers and intractability: A guide to the theory of np-completeness (Michael R. Garey and David S. Johnson). Siam Review, 24(1), 90.
79.
He, Y., Wang, K., Zhang, W., Lin, X., & Zhang, Y. (2021). Exploring cohesive subgraphs with vertex engagement and tie strength in bipartite graphs. Information Sciences, 572, 277–296.MathSciNetCrossRef
89.
Ignatov, D. I., Ivanova, P., & Zamaletdinova, A. (2018). Mixed integer programming for searching maximum quasi-bicliques. In International Conference on Network Analysis (pp. 19–35). Springer.
94.
Kannan, R., & Vinay, V. (1999). Analyzing the structure of large graphs. Rheinische Friedrich-Wilhelms-Universität Bonn, Bonn.
97.
Kumar, R., Tomkins, A., & Vee, E. (2008). Connectivity structure of bipartite graphs via the knc-plot. In WSDM (pp. 129–138).
98.
Lakhotia, K., Kannan, R., Prasanna, V., & De Rose, C. A. (2021). Receipt: Refine coarse-grained independent tasks for parallel tip decomposition of bipartite graphs. PVLDB, 14(3), 404–417.
100.
Ley, M. (2002). The DBLP computer science bibliography: Evolution, research issues, perspectives. In String Processing and Information Retrieval, 9th International Symposium, SPIRE 2002, Lisbon, Portugal, September 11–13, 2002, Proceedings (pp. 1–10).
102.
Li, J., Liu, G., Li, H., & Wong, L. (2007). Maximal biclique subgraphs and closed pattern pairs of the adjacency matrix: A one-to-one correspondence and mining algorithms. TKDE, 19(12), 1625–1637.
103.
Li, M., Hao, J.-K., & Wu, Q. (2020). General swap-based multiple neighborhood adaptive search for the maximum balanced biclique problem. Computers & Operations Research, 119, 104922.MathSciNetCrossRef
109.
Li, Y., Kuboyama, T., & Sakamoto, H. (2013). Truss decomposition for extracting communities in bipartite graph. In Third International Conference on Advances in Information Mining and Management (pp. 76–80).
111.
Liu, B., Yuan, L., Lin, X., Qin, L., Zhang, W., & Zhou, J. (2019). Efficient (α, β)-core computation: An index-based approach. In WWW (pp. 1130–1141).
112.
Liu, B., Yuan, L., Lin, X., Qin, L., Zhang, W., & Zhou, J. (2020). Efficient (α, β)-core computation in bipartite graphs. The VLDB Journal, 29(5), 1075–1099.CrossRef
114.
Liu, G., Sim, K., & Li, J. (2006). Efficient mining of large maximal bicliques. In International Conference on Data Warehousing and Knowledge Discovery (pp. 437–448). Springer.
118.
Liu, X., Li, J., & Wang, L. (2008). Modeling protein interacting groups by quasi-bicliques: Complexity, algorithm, and application. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 7(2), 354–364.
123.
Lyu, B., Qin, L., Lin, X., Zhang, Y., Qian, Z., & Zhou, J. (2020). Maximum biclique search at billion scale. PVLDB, 13(9), 1359–1372.
124.
Ma, C., Fang, Y., Cheng, R., Lakshmanan, L. V., Zhang, W., & Lin, X. (2020). Efficient algorithms for densest subgraph discovery on large directed graphs. In SIGMOD (pp. 1051–1066). ACM.
127.
Ma, Z., Liu, Y., Hu, Y., Yang, J., Liu, C., & Dai, H. (2021). Efficient maintenance for maximal bicliques in bipartite graph streams. In World Wide Web (pp. 1–21).
128.
McCreesh, C., & Prosser, P. (2014). An exact branch and bound algorithm with symmetry breaking for the maximum balanced induced biclique problem. In International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 226–234). Springer.
130.
Mishra, N., Ron, D., & Swaminathan, R. (2004). A new conceptual clustering framework. Machine Learning, 56(1–3), 115–151.CrossRef
131.
Mitzenmacher, M., Pachocki, J., Peng, R., Tsourakakis, C., & Xu, S. C. (2015). Scalable large near-clique detection in large-scale networks via sampling. In SIGKDD (pp. 815–824). ACM.
133.
Mukherjee, A. P., & Tirthapura, S. (2016). Enumerating maximal bicliques from a large graph using mapreduce. IEEE Transactions on Services Computing, 10(5), 771–784.CrossRef
134.
Nussbaum, D., Pu, S., Sack, J.-R., Uno, T., & Zarrabi-Zadeh, H. (2012). Finding maximum edge bicliques in convex bipartite graphs. Algorithmica, 64(2), 311–325.MathSciNetCrossRef
135.
Pandey, A., Sharma, G., & Jain, N. (2020). Maximum weighted edge biclique problem on bipartite graphs. In Conference on Algorithms and Discrete Applied Mathematics (pp. 116–128). Springer.
136.
Pavlopoulos, G. A., Kontou, P. I., Pavlopoulou, A., Bouyioukos, C., Markou, E., & Bagos, P. G. (2018). Bipartite graphs in systems biology and medicine: A survey of methods and applications. GigaScience, 7(4), giy014.
137.
Peeters, R. (2003). The maximum edge biclique problem is np-complete. Discrete Applied Mathematics, 131(3), 651–654.MathSciNetCrossRef
143.
Sarıyüce, A. E., & Pinar, A. (2018). Peeling bipartite networks for dense subgraph discovery. In WSDM (pp. 504–512).
146.
Shaham, E., Yu, H., & Li, X.-L. (2016). On finding the maximum edge biclique in a bipartite graph: A subspace clustering approach. In Proceedings of the 2016 SIAM International Conference on Data Mining (pp. 315–323). SIAM.
149.
Shi, J., & Shun, J. (2020). Parallel algorithms for butterfly computations (pp. 16–30).
150.
Sim, K., Li, J., Gopalkrishnan, V., & Liu, G. (2009). Mining maximal quasi-bicliques: Novel algorithm and applications in the stock market and protein networks. Statistical Analysis and Data Mining: The ASA Data Science Journal, 2(4), 255–273.MathSciNetCrossRef
151.
Sözdinler, M., & Özturan, C. (2018). Finding maximum edge biclique in bipartite networks by integer programming. In 2018 IEEE International Conference on Computational Science and Engineering (CSE) (pp. 132–137). IEEE.
158.
Tahoori, M. B. (2006). Application-independent defect tolerance of reconfigurable nanoarchitectures. ACM Journal on Emerging Technologies in Computing Systems (JETC), 2(3), 197–218.CrossRef
159.
Tan, J. (2008). Inapproximability of maximum weighted edge biclique and its applications. In International Conference on Theory and Applications of Models of Computation (pp. 282–293). Springer.
165.
Wang, J., de Vries, A. P., & Reinders, M. J. T. (2006). Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, Washington, USA, August 6–11, 2006 (pp. 501–508).
167.
Wang, K., Lin, X., Qin, L., Zhang, W., & Ying, Z. (2021). Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. The VLDB Journal 1–24.
168.
Wang, K., Lin, X., Qin, L., Zhang, W., & Zhang, Y. (2019). Vertex priority based butterfly counting for large-scale bipartite networks. PVLDB, 12(10), 1139–1152.
169.
Wang, K., Lin, X., Qin, L., Zhang, W., & Zhang, Y. (2020). Efficient bitruss decomposition for large-scale bipartite graphs. In ICDE (pp. 661–672). IEEE.
170.
Wang, K., Zhang, W., Lin, X., Zhang, Y., Qin, L., & Zhang, Y. (2021). Efficient and effective community search on large-scale bipartite graphs. ICDE.
171.
Wang, K., Zhang, W., Zhang, Y., Qin, L., & Zhang, Y. (2021). Discovering significant communities on bipartite graphs: An index-based approach. TKDE.
173.
Wang, Y., Cai, S., & Yin, M. (2018). New heuristic approaches for maximum balanced biclique problem. Information Sciences, 432, 362–375.MathSciNetCrossRef
177.
Yan, C., Burleigh, J. G., & Eulenstein, O. (2005). Identifying optimal incomplete phylogenetic data sets from sequence databases. Molecular Phylogenetics and Evolution, 35(3), 528–535.CrossRef
179.
Yang, J., Peng, Y., & Zhang, W. (2022). (p,q)-biclique counting and enumeration for large sparse bipartite graphs. PVLDB, 15(2), 141–153.
182.
Yu, K., Long, C., Deepak, P., & Chakraborty, T. (2021). On efficient large maximal biplex discovery. TKDE.
189.
Zhang, Y., Phillips, C. A., Rogers, G. L., Baker, E. J., Chesler, E. J., & Langston, M. A. (2014). On finding bicliques in bipartite graphs: A novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics, 15(1), 110.CrossRef
191.
Zhang, Y., Wang, K., Zhang, W., Lin, X., & Zhang, Y. (2021). Pareto-optimal community search on large bipartite graphs. In CIKM (pp. 2647–2656).
198.
Zhou, Y., & Hao, J.-K. (2019). Tabu search with graph reduction for finding maximum balanced bicliques in bipartite graphs. Engineering Applications of Artificial Intelligence, 77, 86–97.CrossRef
200.
Zhou, Y., Rossi, A., & Hao, J.-K. (2018). Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs. European Journal of Operational Research, 269(3), 834–843.MathSciNetCrossRef
206.
Zou, Z. (2016). Bitruss decomposition of bipartite graphs. In DASFAA (pp. 218–233). Springer.
Metadaten
Titel
CSS on Bipartite Networks
verfasst von
Yixiang Fang
Kai Wang
Xuemin Lin
Wenjie Zhang
Copyright-Jahr
2022
Buch
Cohesive Subgraph Search Over Large Heterogeneous Information Networks

Print ISBN: 978-3-030-97567-8

Electronic ISBN: 978-3-030-97568-5

Copyright-Jahr: 2022

DOI
https://doi.org/10.1007/978-3-030-97568-5_3