{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,30]],"date-time":"2026-08-30T21:52:51Z","timestamp":1788126771651,"version":"build-2803163510"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:p>A bipartite network is a network with two disjoint vertex sets and its edges only exist between vertices from different sets. It has received much interest since it can be used to model the relationship between two different sets of objects in many applications (e.g., the relationship between users and items in E-commerce). In this paper, we study the problem of efficient bi-triangle counting for a large bipartite network, where a bi-triangle is a cycle with three vertices from one vertex set and three vertices from another vertex set. Counting bi-triangles has found many real applications such as computing the transitivity coefficient and clustering coefficient for bipartite networks. To enable efficient bi-triangle counting, we first develop a baseline algorithm relying on the observation that each bi-triangle can be considered as the join of three wedges. Then, we propose a more sophisticated algorithm which regards a bi-triangle as the join of two super-wedges, where a wedge is a path with two edges while a super-wedge is a path with three edges. We further optimize the algorithm by ranking vertices according to their degrees. We have performed extensive experiments on both real and synthetic bipartite networks, where the largest one contains more than one billion edges, and the results show that the proposed solutions are up to five orders of magnitude faster than the baseline method.<\/jats:p>","DOI":"10.14778\/3447689.3447702","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T16:20:06Z","timestamp":1618244406000},"page":"984-996","source":"Crossref","is-referenced-by-count":36,"title":["Efficient bi-triangle counting for large bipartite networks"],"prefix":"10.14778","volume":"14","author":[{"given":"Yixing","family":"Yang","sequence":"first","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maria E.","family":"Orlowska","sequence":"additional","affiliation":[{"name":"Polish-Japanese Institute of Information Technology, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnx001"},{"key":"e_1_2_1_3_1","volume-title":"Modularity and community detection in bipartite networks. Phys. Rev. E 76","author":"Barber Michael J.","year":"2007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.06.052"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125500"},{"key":"e_1_2_1_6_1","unstructured":"Marco Bressan. 2019. Faster Subgraph Counting in Sparse Graphs. In IPEC.  Marco Bressan. 2019. Faster Subgraph Counting in Sparse Graphs. In IPEC."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_9_1","volume-title":"Curvature of co-links uncovers hidden thematic layers in the World Wide Web. PNAS","author":"Eckmann Jean-Pierre","year":"2002"},{"key":"e_1_2_1_10_1","volume-title":"A survey of community search over big graphs. The VLDB Journal","author":"Fang Yixiang","year":"2020"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_13_1","volume-title":"Algorithms and Computation","author":"Floderus Peter"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652181"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80045-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2688283.2688284"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.860472"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_20_1","volume-title":"Aravind Sankar, Yixiang Fang, and Brian YH Lam.","author":"Hu Jiafeng","year":"2019"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882913"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915209"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0459-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339494"},{"key":"e_1_2_1_29_1","volume-title":"Cycles and clustering in bipartite networks. PRE","author":"Lind Pedro","year":"2005"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI-IAT.2009.15"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-syb.2011.0011"},{"key":"e_1_2_1_34_1","volume-title":"Basic notions for the analysis of large two-mode networks. Social Networks 30, 1","author":"Vecchio Matthieu Latapy Nathalie Del","year":"2008"},{"key":"e_1_2_1_35_1","series-title":"SIAM REVIEW 45, 2 (06","volume-title":"The structure and function of complex networks","author":"Newman M. E. J.","year":"2003"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00108"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2011.07.001"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Roger Pearce. 2017. Triangle counting for scale-free graphs at scale in distributed memory. In HPEC. 1--4.  Roger Pearce. 2017. Triangle counting for scale-free graphs at scale in distributed memory. In HPEC. 1--4.","DOI":"10.1109\/HPEC.2017.8091051"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_40_1","volume-title":"David Oliveira Apar\u00edcio, and Fernando M. A. Silva","author":"Pinto Ribeiro Pedro Manuel","year":"2019"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:CMOT.0000032580.12184.c0"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:CMOT.0000032580.12184.c0"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_2_1_45_1","volume-title":"Kolda","author":"Seshadhri C.","year":"2012"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_47_1","unstructured":"Katherine Faust Stanley Wasserman. [n.d.]. Social Network Analysis: Methods and Applications.  Katherine Faust Stanley Wasserman. [n.d.]. Social Network Analysis: Methods and Applications."},{"key":"e_1_2_1_48_1","first-page":"75","article-title":"Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation","volume":"1","author":"Tsourakakis C. E.","year":"2011","journal-title":"SNAM"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00030"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","volume-title":"Efficient bitruss decomposition for large-scale bipartite graphs","author":"Wang Kai","DOI":"10.1109\/ICDE48307.2020.00063"},{"key":"e_1_2_1_53_1","volume-title":"Efficient Bitruss Decomposition for Large-scale Bipartite Graphs. In ICDE","author":"Wang Kai","year":"2020"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2756836"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2013.030514.131312"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2911996.2912035"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_58_1","unstructured":"Yixing Yang Yixiang Fang Maria E. Orlowska Wenjie Zhang Xuemin Lin. [n.d.]. Efficient Bi-triangle Counting for Large Bipartite Networks (Technical report). http:\/\/www.cse.unsw.edu.au\/~z5151364\/technique_report.pdf.  Yixing Yang Yixiang Fang Maria E. Orlowska Wenjie Zhang Xuemin Lin. [n.d.]. Efficient Bi-triangle Counting for Large Bipartite Networks (Technical report). http:\/\/www.cse.unsw.edu.au\/~z5151364\/technique_report.pdf."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32049-6_14"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3447689.3447702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:19:09Z","timestamp":1672226349000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3447689.3447702"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2]]},"references-count":59,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10.14778\/3447689.3447702"],"URL":"https:\/\/doi.org\/10.14778\/3447689.3447702","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,2]]}}}