Structural Analysis of Complex Networks
Because of the increasing complexity and growth of real-world networks, their analysis by using classical graph-theoretic methods is oftentimes a difficult procedure. As a result, there is a strong need to combine graph-theoretic methods with mathematical
- PDF / 429,605 Bytes
- 26 Pages / 439 x 666 pts Page_size
- 20 Downloads / 216 Views
A Brief Introduction to Complex Networks and Their Analysis Frank Emmert-Streib
Abstract In this chapter we present a brief introduction to complex networks and their analysis. We review important network classes and properties thereof as well as general analysis methods. The focus of this chapter is on the structural analysis of networks, however, information-theoretic methods are also discussed. Keywords Complex networks Centrality measures Comparative network analysis Module detection Information-theoretic measures MSC2000: Primary 05C90; Secondary 65C60, 46N60, 94A17
1.1 Introduction Discrete objects representing graphs have been studied for a long time. Among the first who studied graphs are Euler [56] and Cayley [30]. Interestingly, the origin of the term graph dates back to K¨onig in the 1930s [81], less than 100 years ago. The interest in graphs and their analysis is manifold. From a theoretical point of view the categorization and the analysis of properties of graphs [20, 44, 54, 70] as well as the development of graph algorithms [37, 57] are important problems that have been studied extensively. From an applied point of view it has been realized that graphs can represent physical [70], biological [51, 78, 101], or sociological objects [68, 104], e.g., a crystal or protein structure or the acquaintance network among a group of people. Recently, networks have been also employed in data analysis and machine learning [3, 51, 99]. In the following we use the terms graph and network interchangeably although they do not mean precisely the same thing. Usually,
F. Emmert-Streib () Computational Biology and Machine Learning, Center for Cancer Research and Cell Biology, School of Medicine, Dentistry and Biomedical Sciences, Queen’s University Belfast, 97 Lisburn Road, Belfast BT9 7BL, UK e-mail: [email protected]
M. Dehmer (ed.), Structural Analysis of Complex Networks, c Springer Science+Business Media, LLC 2011 DOI 10.1007/978-0-8176-4789-6 1,
1
2
F. Emmert-Streib
a graph refers first of all to a mathematical object regardless of its realization in, e.g., nature, whereas a network represents a “real-world” object rather than a pure mathematical one. Because we want to focus on applied aspects of graphs most of the time we prefer the expression network. In this chapter we provide a brief introduction to complex networks and their analysis. In Sect. 1.2 we review some important network classes. In Sect. 1.3 we present some methods for the structural analysis of networks that help, e.g., to characterize them as a whole or allow us to identify specific nodes in the network with certain properties. In Sect. 1.3.5 we present important methods to analyze networks comparatively. This means that means these measures always compare two graphs with each other and provide, hence, similarity or dissimilarity measures for this comparison. Such methods are especially useful for data analysis or machine learning because they allow a combination with, e.g., clustering methods to extract regularities from the
Data Loading...
