abstract: Measuring node centrality is a critical common denominator behind many important graph mining tasks. While the existing literature offers a wealth of different node centrality measures, it remains a daunting task on how to intervene the node centrality in a desired way. In this thesis, we study the problem of minimizing the centrality of one or more target nodes by edge operation. The heart of the proposed method is an accurate and efficient algorithm to estimate the impact of edge deletion on the spectrum of the underlying network, based on the observation that the edge deletion is essentially a local, sparse perturbation to the original network. Extensive experiments are conducted on a diverse set of real networks to demonstrate the effectiveness, efficiency and scalability of our approach. In particular, it is average of 260.95%, in terms of minimizing eigen-centrality, better than the standard matrix-perturbation based algorithm, with lower time complexity. / Dissertation/Thesis / Masters Thesis Computer Science 2016
| Identifer | oai:union.ndltd.org:asu.edu/item:40757 |
| Date | January 2016 |
| Contributors | Peng, Ruiyue (Author), Tong, Hanghang (Advisor), He, Jingrui (Committee member), Davulcu, Hasan (Committee member), Arizona State University (Publisher) |
| Source Sets | Arizona State University |
| Language | English |
| Detected Language | English |
| Type | Masters Thesis |
| Format | 50 pages |
| Rights | http://rightsstatements.org/vocab/InC/1.0/, All Rights Reserved |
Page generated in 0.0016 seconds