Efficient Maximum Closeness Centrality Group Identification

Chen, C; Wang, W; Wang, X

Efficient Maximum Closeness Centrality Group Identification

Chen, C Wang, W Wang, X

Permalink

Publisher:: Springer
Publication Type:: Conference Proceeding
Citation:: Databases Theory and Applications, 2016, 9877 pp. 43 - 55
Issue Date:: 2016

Closed Access

	Filename	Description	Size
	DocumentOpener (11).pdf	Published version	753.68 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	Chen, C	en_US
dc.contributor.author	Wang, W	en_US
dc.contributor.author	Wang, X	en_US
dc.contributor.editor	Cheema, MA	en_US
dc.contributor.editor	Zhang, W	en_US
dc.contributor.editor	Chang, L	en_US
dc.date	2016-09-28	en_US
dc.date.issued	2016	en_US
dc.identifier.citation	Databases Theory and Applications, 2016, 9877 pp. 43 - 55	en_US
dc.identifier.isbn	978-3-319-46921-8	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/103203
dc.description.abstract	As a key concept in the social networks, closeness centrality is widely adopted to measure the importance of a node. Many efficient algorithms are developed in the literature to find the top-k closeness centrality nodes. In most of the previous work, nodes are treated as irrelevant individuals for a top-k ranking. However, in many applications, it is required to find a set of nodes that is the most important as a group. In this paper, we extend the concept of closeness centrality to a set of nodes. We aim to find a set of k nodes that has the largest closeness centrality as a whole. We show that the problem is NP-hard, and prove that the objective function is monotonic and submodular. Therefore, the greedy algorithm can return a result with 1−1/e1−1/e approximation ratio. In order to handle large graphs, we propose a baseline sampling algorithm (BSA). We further improve the sampling approach by considering the order of samples and reducing the marginal gain update cost, which leads to our order based sampling algorithm (OSA). Finally, extensive experiments on four real world social networks demonstrate the efficiency and effectiveness of the proposed methods.	en_US
dc.publisher	Springer	en_US
dc.relation.ispartof	Databases Theory and Applications	en_US
dc.relation.ispartof	Australasian Database Conference	en_US
dc.relation.isbasedon	10.1007/978-3-319-46922-5_4	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Efficient Maximum Closeness Centrality Group Identification	en_US
dc.type	Conference Proceeding
utslib.citation.volume	9877	en_US
utslib.location.activity	Sydney, NSW	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
utslib.copyright.status	closed_access
pubs.consider-herdc	true	en_US
pubs.finish-date	2016-09-29	en_US
pubs.publication-status	Published	en_US
pubs.start-date	2016-09-28	en_US
pubs.volume	9877	en_US

Abstract:

As a key concept in the social networks, closeness centrality is widely adopted to measure the importance of a node. Many efficient algorithms are developed in the literature to find the top-k closeness centrality nodes. In most of the previous work, nodes are treated as irrelevant individuals for a top-k ranking. However, in many applications, it is required to find a set of nodes that is the most important as a group. In this paper, we extend the concept of closeness centrality to a set of nodes. We aim to find a set of k nodes that has the largest closeness centrality as a whole. We show that the problem is NP-hard, and prove that the objective function is monotonic and submodular. Therefore, the greedy algorithm can return a result with 1−1/e1−1/e approximation ratio. In order to handle large graphs, we propose a baseline sampling algorithm (BSA). We further improve the sampling approach by considering the order of samples and reducing the marginal gain update cost, which leads to our order based sampling algorithm (OSA). Finally, extensive experiments on four real world social networks demonstrate the efficiency and effectiveness of the proposed methods.

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

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