Querying K-truss community in large and dynamic graphs

Huang, X; Cheng, H; Qin, L; Tian, W; Yu, JX

Querying K-truss community in large and dynamic graphs

Huang, X Cheng, H Qin, L

Tian, W Yu, JX

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, pp. 1311 - 1322
Issue Date:: 2014-01-01

Closed Access

	Filename	Description	Size
	[2014 SIGMOD] Querying K-Truss Community in Large and Dynamic Graphs.pdf	Published version	328.27 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	Huang, X	en_US
dc.contributor.author	Cheng, H	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.contributor.author	Tian, W	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.date.issued	2014-01-01	en_US
dc.identifier.citation	Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, pp. 1311 - 1322	en_US
dc.identifier.isbn	9781450323765	en_US
dc.identifier.issn	0730-8078	en_US
dc.identifier.uri	http://hdl.handle.net/10453/35407
dc.description.abstract	Community detection which discovers densely connected structures in a network has been studied a lot. In this paper, we study online community search which is practically useful but less studied in the literature. Given a query vertex in a graph, the problem is to find meaningful communities that the vertex belongs to in an online manner. We propose a novel community model based on the κ-truss concept, which brings nice structural and computational properties. We design a compact and elegant index structure which supports the efficient search of κ-truss communities with a linear cost with respect to the community size. In addition, we investigate the κ truss community search problem in a dynamic graph setting with frequent insertions and deletions of graph vertices and edges. Extensive experiments on large real-world networks demonstrate the effectiveness and efficiency of our community model and search algorithms. © 2014 ACM.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DE140100999
dc.relation.ispartof	Proceedings of the ACM SIGMOD International Conference on Management of Data	en_US
dc.relation.isbasedon	10.1145/2588555.2610495	en_US
dc.title	Querying K-truss community in large and dynamic graphs	en_US
dc.type	Conference Proceeding
utslib.for	080101 Adaptive Agents and Intelligent Robotics	en_US
utslib.for	080109 Pattern Recognition and Data Mining	en_US
pubs.embargo.period	Not known	en_US
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 - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

Community detection which discovers densely connected structures in a network has been studied a lot. In this paper, we study online community search which is practically useful but less studied in the literature. Given a query vertex in a graph, the problem is to find meaningful communities that the vertex belongs to in an online manner. We propose a novel community model based on the κ-truss concept, which brings nice structural and computational properties. We design a compact and elegant index structure which supports the efficient search of κ-truss communities with a linear cost with respect to the community size. In addition, we investigate the κ truss community search problem in a dynamic graph setting with frequent insertions and deletions of graph vertices and edges. Extensive experiments on large real-world networks demonstrate the effectiveness and efficiency of our community model and search algorithms. © 2014 ACM.

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

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