| 摘要(英) |
In network analysis, betweenness centrality is essential for researchers to measure the importance of each parts of the network and find out the part to be study further. Betweenness centrality has a widespread use, but it is costly to compute. Currently, the fastest known algorithm requires Ο(|V|2logV+VE) time on weighted graph and Ο(VE) time on unweighted graph. But in some applications, such as the algorithm of Girvan and Newman, still cost too much time for computing.
Girvan and Newman thought that the edge which has the higher betweenness centrality has more probability to be the edge which connects two communities. According to this, they designed an algorithm which does the operation “compute the betweenness centrality of all edges → remove the edge which has the highest betweenness centrality” repeatedly and then constructs a dendrogram which represents the hierarchical relationships between the vertices of the network.
In this thesis, we use a random sampling heuristic betweenness centrality computation to accelerate the speed of finding the edge which has the maximum betweenness centrality. This can also be used to speed up the algorithm of Girvan and Newman. Besides, we also design an improved exact betweenness centrality compute which is suitable for decremental networks to accelerate the algorithm of Girvan and Newman. We test the improved algorithm on 11 random generated networks and 5 non-random generated networks. On random generated networks, we gained a maximum speedup about 34 times. On non-random generated networks, we gained a maximum speedup about 15 times.
|
| 參考文獻 |
J. M. Anthonisse: The rush in a directed graph. Technical Report BN 9/71, Stichting Mathematisch Centrum, Amsterdam (1971)
N. Biggs, E. Lloyd and R. Wilson: Graph Theory, 1736-1936. Oxford University Press (1986)
Ulrik Brandes and Christian Pich: Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos, special issue on Complex Networks' Structure and Dynamics. (2007)
Ulrik Brandes: A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25, 163 (2001)
C.M. Deane, L. Salwinski, I. Xenarios and D. Eisenberg: Protein interactions: two methods for assessment of the reliability of high throughput observations. Cell Proteomics, 1, 349–356. (2002)
P. Erdos and A. Renyi: On random graphs, Publicationes Mathematicae 6, 290–297 (1959).
David Eppstein and Joseph Wang: Fast Approximation of Centrality. Journal of Graph Algorithms and Applications, 8(1):39–45. (2004)
L. C. Freeman: A set of measures of centrality based on betweenness. Sociometry, 40:35-41 (1977)
Feng Luo, Yunfeng Yang, Roger Chang, Jizhong Zhou, and Richard H. Scheuermann: Modular organization of protein interaction networks. Bioinformatics, Vol. 23 no. 2, 207–214 (2007).
M. Girvan and M. E. J. Newman: Community structure in social and biological networks. Proceedings of the National Academy of Sciences USA 99(12) (2002) 7821-7826
Jonathan L. Gross and Jay Yellen: Handbook of graph theory. 2004
P. Hage and F. Harary: Eccentricity and centrality in networks. Social Networks, 17:57-63 (1995)
Monika R. Henzingera, Philip Kleinb, Satish Raoc and Sairam Subramanian: Faster shortest-path algorithms for planar graphs, J. Comput. Syst. Sci, 53, 2-23, 1997.
Maliackal Poulo Joy, Amy Brock, Donald E. Ingber, and Sui Huang: High-betweenness proteins in the yeast protein interaction network. J. Biomed. Biotechnol. (2005), 96–103
H. Jeong, S. P. Mason, A.-L. Barabási, and Z. N. Oltvai: Lethality and centrality in protein networks. Nature, 411:41–42. Brief communications. (2001)
M. E. J. Newman and M. Girvan: Finding and evaluating community structure in networks. PHYSICAL REVIEW E 69, 026113 (2004)
J. Niemincn: On centrality in a graph. Scandinavian Journal of Psychology 15:322-336. (1974)
S. Pettie: A new approach to all-pairs shortest paths on real-weighted graphs, Theoret. Comput. Sci., 312:47-74, 2004.
Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi: Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA 101, 2658–2663 (2004).
G. Sabidussi: The centrality index of a graph. Psychometrika, 31:581-603 (1966)
A. Shimbel: Structural parameters of communication networks. Bulletin of Mathematical Biophysics, 15:501-507 (1953)
M. Thorup: Undirected single-source shortest path with positive integer weights in linear time, J. ACM, 46(3):362-394, 1999.
Joshua R. Tyler, Dennis M. Wilkinson, and Bernardo A. Huberman: Email as spectroscopy: Automated discovery of community structure within organizations. In M. Huysman, E. Wenger, and V. Wulf (eds.), Proceedings of the First International Conference on Communities and Technologies, Kluwer, Dordrecht (2003).
Elizabeth A. Winzeler, et al: Functional characterization of the Saccharomyces cerevisiae genome by gene deletion and parallel analysis. Science, 285, 901–906, 1999.
D. J. Watts and S. H. Strogatz: Collective dynamics of `small-world' networks, Nature 393, 440-442 (1998).
W. W. Zachary: J. Anthropol. Res. 33, 452–473 (1977)
|
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit