Publication:
Efficient computation of cohesive subgraphs on bipartite graphs

dc.contributor.advisor Zhang, Wenjie en_US
dc.contributor.advisor Li, Binghao en_US
dc.contributor.advisor Lin, Xuemin en_US
dc.contributor.author He, Yizhang en_US
dc.date.accessioned 2022-03-15T08:50:24Z
dc.date.available 2022-03-15T08:50:24Z
dc.date.issued 2021 en_US
dc.description.abstract A bipartite graph is a graph with two layers such that vertices in the same layer are not connected, which is widely used to model the relationships among two types of entities. Examples of bipartite graphs include author-paper networks, customer-product networks, and ecological networks (e.g., the predator-prey network and the plant-animal network). In bipartite graphs, cohesive subgraph computation is a fundamental problem that aims to find closely-connected subgraphs, which can be applied to group recommendations, network visualization, and fraud detection. In this thesis, we propose a novel cohesive subgraph model called τ -strengthened (α, β)- core (denoted as (α, β)τ -core), which is the first work to consider both tie strength and vertex engagement on bipartite graphs. An edge is a strong tie if contained in at least τ butterflies (2 x 2-bicliques). (α, β)τ -core requires each vertex on the upper or lower level to have at least α or β strong ties, given strength level τ. To retrieve the vertices of (α, β)τ -core optimally, we construct index Iα,β,τ to store all (α, β)τ -cores. Effective optimization techniques are proposed to improve index construction. To make our idea practical on large graphs, we propose 2D-indexes Iα,β, Iβ,τ, and Iα,τ that selectively store the vertices of (α, β)τ -core for some α, β, and τ . The 2D-indexes are more space-efficient and require less construction time, each of which can support (α, β)τ -core queries. As query efficiency depends on input parameters and the choice of 2D-index, we propose a learning-based hybrid computation paradigm by training a feed-forward neural network to predict the optimal choice of 2D-index that minimizes the query time. Extensive experiments show that (1) (α, β)τ -core is an effective model capturing unique and important the proposed techniques significantly improve the efficiency of index construction and query processing. en_US
dc.identifier.uri http://hdl.handle.net/1959.4/71100
dc.language English
dc.language.iso EN en_US
dc.publisher UNSW, Sydney en_US
dc.rights CC BY-NC-ND 3.0 en_US
dc.rights.uri https://creativecommons.org/licenses/by-nc-nd/3.0/au/ en_US
dc.subject.other Cohesive subgraph mining en_US
dc.subject.other Bipartite graph en_US
dc.title Efficient computation of cohesive subgraphs on bipartite graphs en_US
dc.type Thesis en_US
dcterms.accessRights open access
dcterms.rightsHolder He, Yizhang
dspace.entity.type Publication en_US
unsw.accessRights.uri https://purl.org/coar/access_right/c_abf2
unsw.date.embargo 2023-09-27 en_US
unsw.description.embargoNote Embargoed until 2023-09-27
unsw.identifier.doi https://doi.org/10.26190/unsworks/2350
unsw.relation.faculty Engineering
unsw.relation.originalPublicationAffiliation He, Yizhang, School of Computer Science and Engineering, Engineering, UNSW en_US
unsw.relation.originalPublicationAffiliation Zhang, Wenjie, School of Computer Science and Engineering, Engineering, UNSW en_US
unsw.relation.originalPublicationAffiliation Li, Binghao, School of Minerals and Energy Resources Engineering, Engineering, UNSW en_US
unsw.relation.originalPublicationAffiliation Lin, Xuemin, School of Computer Science and Engineering, Engineering, UNSW en_US
unsw.relation.school School of Computer Science and Engineering *
unsw.thesis.degreetype Masters Thesis en_US
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
public version.pdf
Size:
4.75 MB
Format:
application/pdf
Description:
Resource type