# Quelle:Nm/Holmgren 2006

## < Quelle:Nm

31.558Seiten in
diesem Wiki

Angaben zur Quelle [Bearbeiten]

 Autor Åke J. Holmgren Titel Using Graph Models to Analyze the Vulnerability of Electric Power Networks Zeitschrift Risk Analysis Verlag Wiley Jahr 2006 Nummer 26 (4) Seiten 955-969 DOI 10.1111/j.1539-6924.2006.00791.x URL http://onlinelibrary.wiley.com/doi/10.1111/j.1539-6924.2006.00791.x/abstract? Literaturverz. no Fußnoten no Fragmente 3

Fragmente der Quelle:
 Zuletzt bearbeitet: 2012-04-19 22:32:36 Hindemith

 Typus KomplettPlagiat Bearbeiter Graf Isolan Gesichtet
Untersuchte Arbeit:
Seite: 111, Zeilen: 17-27
Quelle: Holmgren 2006
Seite(n): 956, Zeilen: right column 18-32
In graph theory a number of measures have been proposed to characterize networks. However, three concepts are particularly important in contemporary studies of the topology of complex networks: degree distribution, clustering coefficient, and average path length (Albert, R., and Barabasi, A.L. (2002); Dorogovtsev, S. N., and Mendes, J. F. F. (2002); Newman, M. E. J. (2003)).

3.4.1 Degree Distribution

The degree $k_i$ is the number of edges connecting to the i$^{th}$ vertex. The vertex degree is characterized by a distribution function P(k), which gives the probability that a randomly selected vertex has k edges. Recent studies show that several complex networks have a [heterogeneous topology, i.e., some vertices have a very large number of edges, but the majority of the vertices only have a few edges.]

In graph theory, a number of measures have been proposed to characterize networks. However, three concepts are particularly important in contemporary studies of the topology of complex networks: degree distribution, clustering coefficient, and average path length. [EN 1-3]

2.2.1. Degree Distribution

The degree $k_i$ is the number of edges connecting to vertex i. The vertex degree is characterized by a distribution function P(k), which gives the probability that a randomly selected vertex has k edges. Recent studies show that several complex networks have a heterogeneous topology, i.e., some vertices have a very large number of edges, but the majority of the vertices only have a few edges.

[EN 1]. Albert, R., & Barabási, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47–97.

[EN 2]. Dorogovtsev, S. N., & Mendes, J. F. F. (2002). Evolution of networks. Advances in Physics, 51, 1079–1187.

[EN 3]. Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45, 167–256.

 Anmerkungen Nearly identical, though the source is not mentioned anzwhere. Sichter (Graf Isolan), Hindemith

 Zuletzt bearbeitet: 2012-04-19 22:38:39 Hindemith

 Typus KomplettPlagiat Bearbeiter Graf Isolan Gesichtet
Untersuchte Arbeit:
Seite: 112, Zeilen: 1-27
Quelle: Holmgren 2006
Seite(n): 956-957, Zeilen: p.956, right column 28-45 - p.957, left column 1-18
[Recent studies show that several complex networks have a] heterogeneous topology, i.e., some vertices have a very large number of edges, but the majority of the vertices only have a few edges. That is, the degree distribution follows a power law $P(k)\cup k^{-\gamma}$ for large k(i.e., $P(k)/ k^{-\gamma} \to 1$ when $k\to \infty$). The average degree (k) of a graph with N vertices and M edges is (k) = 2M / N.

3.4.2 Clustering Coefficient

Many complex networks exhibit an inherent tendency to cluster. In social networks this represents a circles of friends in which every member knows each other. The clustering coefficient is a local property capturing “the density” of triangles in a graph, i.e., two vertices that both are connected to a third vertex are also directly connected to each other. An $i^{th}$ vertex in a network has $k_i$ edges that connects it to $k_i$ other vertices. The maximum possible number of edges between the $k_i$ neighbours is ${k_i \choose 2}=k_i (k_i-1) / 2.$ The clustering coefficient of $i^{th}$ vertex is defined as the ratio between the number $M_i$ of edges that actually exist between these $k_i$ vertices and the maximum possible number of edges, i.e., $C_i = 2 M_i / k_i(k_i-1).$ The clustering coefficient of the whole network

$C = (1/N)\sum_{i=1}^{n}{\mathcal C}_{i} \sum_{i=1}^{n} C_i$

3.4.3 Average Path Length

The distance $l_{uv}$ between two vertices u and v is defined as the number of edges along the shortest path connecting them. The average path length $l = (l_{uv}) = [1 / N (N - 1)] \sum_{u\neq v\in V}l_{uv}$ is a measure of how a network is scattered. Sometimes, the diameter d of a graph is defined as the maximum path length between any two connected vertices in the graph. However, in other situations the concept diameter relate to the average path length, i.e., d = l.

[p. 956]

Recent studies show that several complex networks have a heterogeneous topology, i.e., some vertices have a very large number of edges, but the majority of the vertices only have a few edges. That is, the degree distribution follows a power law $P(k)\cup k^{-\gamma}$ for large k(i.e., $P(k)/ k^{-\gamma} \to 1$ when $k\to \infty$). The average degree (k) of a graph with N vertices and M edges is (k) = 2M/N.

2.2.2. Clustering Coefficient

Many complex networks exhibit an inherent tendency to cluster. In social networks this represents circles of friends in which every member knows each other. The clustering coefficient is a local property capturing “the density” of triangles in the graph, i.e., two vertices that both are connected to a third vertex are also directly connected to each other. A vertex i in the network has $k_i$ edges that connects it to

[p. 957]

$k_i$ other vertices. The maximum possible number of edges between the ki neighbors is ${k_i \choose 2}=k_i(k_i-1)/2.$ The clustering coefficient of vertex i is defined as the ratio between the number $M_i$ of edges that actually exist between these $k_i$ vertices and the maximum possible number of edges, i.e., $C_i = 2 M_i / k_i(k_i-1).$ The clustering coefficient of the whole network $C = (1/N)\sum_i {\mathcal C}_i.$

2.2.3. Average Path Length

The distance $l_{uv}$ between two vertices u and v is defined as the number of edges along the shortest path connecting them. The average path length $l = (l_{uv}) = [1 / N (N - 1)] \sum_{u\neq v\in V}l_{uv}$ is a measure of how the network is scattered. Sometimes, the diameter d of a graph is defined as the maximum path length between any two connected vertices in the graph. However, in other situations the concept diameter relate to the average path length, i.e., d = l.

 Anmerkungen The copying process continues with Nm introducing an unfortunate mistake in the formula for the clustering coefficient. Apart from this mistake, both texts are nearly identical. Sichter (Graf Isolan), Hindemith

 Zuletzt bearbeitet: 2012-04-19 22:41:53 Hindemith

 Typus KomplettPlagiat Bearbeiter Graf Isolan Gesichtet
Untersuchte Arbeit:
Seite: 113, Zeilen: 1-22
Quelle: Holmgren 2006
Seite(n): 957, Zeilen: left column 18-42
[The] so-called small-world property appears to characterize many complex networks. Despite their often-large size, there is a relatively short path between any two vertices in a network: the average shortest paths between a pair of vertices scales as the logarithm of the number of vertices.

3.5 GRAPHS AS MODELS OF REAL-WORLD NETWORKS

The study of networks, and in particular the interest in the statistical measures of the topology of networks (see section 3.4), has given birth to three main classes of network models. The random graph was introduced by Erdos and Renyi in the late 1950s and is one of the earliest theoretical models of a network (Bollobas, B., 1985). This is the easiest model to analyze mathematically and it can serve as a reference for randomness. Watts and Strogatz introduced the so called small world model in 1998 (Watts, D. J., and Strogatz, S. H., 1998). This model combines high clustering and a short average path length.

In 1999, Barabasi and Albert (BA) addressed the origin of the power-law degree distribution, evident in many real networks, with a simple model (also known as the scale-free network model) that put the emphasis on how real networks evolve (Albert, R., Jeong, H., and Barabasi, A.L., 2000).

The so-called small-world property appears to characterize many complex networks. Despite their often-large size, there is a relatively short path between any two vertices in the network: the average shortest paths between

a pair of vertices scales as the logarithm of the number of vertices.

2.3. Graphs as Models of Real-World Networks

2.3.1. Theoretical Network Models

The study of networks, and in particular the interest in the statistical measures of the topology of networks (previous section), has given birth to three main classes of network models. The random graph was introduced by Erdös and Rènyi in the late 1950s and is one of the earliest theoretical models of a network. [EN 12] This is the easiest model to analyze mathematically and it can serve as a reference for randomness. Watts and Strogatz introduced the so-called small world model in 1998. [EN 4] This model combines high clustering and a short average path length. In 1999, Barabási and Albert (BA) addressed the origin of the power-law degree distribution, evident in many real networks, with a simple model (also known as the scale-free network model) that put the emphasis on how real networks evolve. [EN 13]

---

[EN 4]. Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of “small-world” networks. Nature, 393, 440–442.

[EN 12]. Bollobás, B. (1985). Random Graphs. London: Academic Press.

[EN 13]. Albert, R., Jeong, H., & Barabási, A.-L. (2000). Error and attack tolerance of complex networks. Nature, 406, 378–382.

 Anmerkungen The third page of text which is identical to Holmgren (2006). No source given. Sichter (Graf Isolan), Hindemith