The Library
Using geodesic space density gradients for network community detection
Tools
Mahmood, Arif, Small, Michael, Al-Maadeed, Somaya and Rajpoot, Nasir M. (2017) Using geodesic space density gradients for network community detection. IEEE Transactions on Knowledge and Data Engineering, 294 (4). pp. 921-935. doi:10.1109/TKDE.2016.2632716 ISSN 1041-4347.
|
PDF
WRAP-using-geodesic-space-gradients-detection-Rajpoot-2017.pdf - Accepted Version - Requires a PDF viewer. Download (4Mb) | Preview |
Official URL: http://doi.org/10.1109/TKDE.2016.2632716
Abstract
Many real world complex systems naturally map to network data structures instead of geometric spaces because the only available information is the presence or absence of a link between two entities in the system. To enable data mining techniques to solve problems in the network domain, the nodes need to be mapped to a geometric space. We propose this mapping by representing each network node with its geodesic distances from all other nodes. The space spanned by the geodesic distance vectors is the geodesic space of that network. Position of different nodes in the geodesic space encode the network structure. In this space, considering a continuous density field induced by each node, density at a specific point is the summation of density fields induced by all nodes. We drift each node in the direction of positive density gradient using an iterative algorithm till each node reaches a local maximum. Due to the network structure captured by this space, the nodes that drift to the same region of space belong to the same communities in the original network. We use the direction of movement and final position of each node as important clues for community membership assignment. The proposed algorithm is compared with more than ten state of the art community detection techniques on two benchmark networks with known communities using Normalized Mutual Information criterion. The proposed algorithm outperformed these methods by a significant margin. Moreover, the proposed algorithm has also shown excellent performance on many real-world networks.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Data mining, G-spaces | ||||||||
Journal or Publication Title: | IEEE Transactions on Knowledge and Data Engineering | ||||||||
Publisher: | IEEE Computer Society | ||||||||
ISSN: | 1041-4347 | ||||||||
Official Date: | 1 April 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 294 | ||||||||
Number: | 4 | ||||||||
Page Range: | pp. 921-935 | ||||||||
DOI: | 10.1109/TKDE.2016.2632716 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 24 November 2016 | ||||||||
Date of first compliant Open Access: | 14 June 2017 | ||||||||
Funder: | Australian Research Council (ARC) | ||||||||
Grant number: | Discovery Project (DP140100203), Future Fellowship (FT110100896) | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year