Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs

Wang, K; Zhang, W; Lin, X; Zhang, Y; Li, S

Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs

Wang, K Zhang, W Lin, X Zhang, Y

Li, S

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: 2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, 2022-May, pp. 2291-2305
Issue Date:: 2022

Closed Access

	Filename	Description	Size
	Discovering_Hierarchy_of_Bipartite_Graphs_with_Cohesive_Subgraphs.pdf	Published version	528.17 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Wang, K
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Li, S
dc.date	2022-05-09
dc.date.accessioned	2023-06-28T02:59:23Z
dc.date.available	2023-06-28T02:59:23Z
dc.date.issued	2022
dc.identifier.citation	2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, 2022-May, pp. 2291-2305
dc.identifier.isbn	978-1-6654-0883-7
dc.identifier.issn	1063-6382
dc.identifier.issn	2375-026X
dc.identifier.uri	http://hdl.handle.net/10453/170931
dc.description.abstract	Bipartite graph is a widely used model to describe relationships between two different types of entities Exploring graph hierarchy with cohesive subgraphs has been extensively studied on unipartite graphs while only a few works focus on bipartite graphs In this paper we propose the bipartite hierarchy which is the first model to discover the hierarchical structure of bipartite graphs based on the concept of alpha 2 beta core and graph connectivity Notably alpha beta text core is a vertex centric model that conforms to the special structure of bipartite graphs i e formed by two different vertex layers Accordingly the bipartite hierarchy has two parts i e the upper and lower hierarchies to record the hierarchical relationships among upper and lower vertices respectively We theoretically prove that the bipartite hierarchy is space efficient i e its space cost is linear to the graph size and clearly illustrate its structure via visualization In addition efficient algorithms for building the bipartite hierarchy are proposed by utilizing the nested property of alpha beta text core Since bipartite graphs can be dynamically changed in real world scenarios we also study the bipartite hierarchy maintenance algorithms against the edge insertion deletion cases These algorithms can effectively identify the affected regions to limit computation scope and avoid re building the bipartite hierarchy from scratch Extensive experiments on 10 real world graphs not only demonstrate the effectiveness of the proposed bipartite hierarchy but also validate the efficiency of our hierarchy construction and maintenance algorithms
dc.language	en
dc.publisher	IEEE
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation.ispartof	2022 IEEE 38th International Conference on Data Engineering (ICDE)
dc.relation.ispartof	IEEE International Conference on Data Engineering
dc.relation.isbasedon	10.1109/icde53745.2022.00217
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs
dc.type	Conference Proceeding
utslib.citation.volume	2022-May
utslib.location.activity	Kuala Lumpur, Malaysia
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	closed_access	*
pubs.consider-herdc	false
dc.date.updated	2023-06-28T02:59:22Z
pubs.finish-date	2022-05-12
pubs.place-of-publication	Piscataway, USA
pubs.publication-status	Published
pubs.start-date	2022-05-09
pubs.volume	2022-May
dc.location	Piscataway, USA

Abstract:

Bipartite graph is a widely used model to describe relationships between two different types of entities Exploring graph hierarchy with cohesive subgraphs has been extensively studied on unipartite graphs while only a few works focus on bipartite graphs In this paper we propose the bipartite hierarchy which is the first model to discover the hierarchical structure of bipartite graphs based on the concept of alpha 2 beta core and graph connectivity Notably alpha beta text core is a vertex centric model that conforms to the special structure of bipartite graphs i e formed by two different vertex layers Accordingly the bipartite hierarchy has two parts i e the upper and lower hierarchies to record the hierarchical relationships among upper and lower vertices respectively We theoretically prove that the bipartite hierarchy is space efficient i e its space cost is linear to the graph size and clearly illustrate its structure via visualization In addition efficient algorithms for building the bipartite hierarchy are proposed by utilizing the nested property of alpha beta text core Since bipartite graphs can be dynamically changed in real world scenarios we also study the bipartite hierarchy maintenance algorithms against the edge insertion deletion cases These algorithms can effectively identify the affected regions to limit computation scope and avoid re building the bipartite hierarchy from scratch Extensive experiments on 10 real world graphs not only demonstrate the effectiveness of the proposed bipartite hierarchy but also validate the efficiency of our hierarchy construction and maintenance algorithms

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/170931