## FANDOM

33.125 Seiten

Angaben zur Quelle [Bearbeiten]

 Autor Stephen P. Borgatti Titel Graph Theory Jahr 2002 Anmerkung Notes from the CASOS Institute 2002 - Reading List; NM hat den identischen Text auch 2008 publiziert: http://nguyendangbinh.org/Proceedings/IPCV08/Papers/ICA4831.pdf URL http://www.casos.cs.cmu.edu/events/summer_institute/2002/reading_list/borgatti/graphtheory.pdf Literaturverz. no Fußnoten no Fragmente 5

Fragmente der Quelle:
 Zuletzt bearbeitet: 2012-04-26 19:55:43 WiseWoman

 Typus KomplettPlagiat Bearbeiter Hindemith Gesichtet
Untersuchte Arbeit:
Seite: 95, Zeilen: 12-15
Quelle: Borgatti_2002
Seite(n): 1, Zeilen: 8-10
Graph Theory [FN 14]

The fundamental concept of graph theory is a graph, which (despite the name) is best thought of as a mathematical object rather than a diagram, even though graphs have a very natural graphical representation.

[FN 14] Most of the concepts discussed in this section are taken from West B. Douglas (2001).

Graphs

The fundamental concept of graph theory is the graph, which (despite the name) is best thought of as a mathematical object rather than a diagram, even though graphs have a very natural graphical representation.

 Anmerkungen The source is not given. West B. Douglas is listed in the bibliography under "West", but the author is named Douglas B. West and the book was published in 1996 (2nd edition was 2001): http://www.math.uiuc.edu/~west/igt/ Sichter (Hindemith), WiseWoman

 Zuletzt bearbeitet: 2012-04-26 19:43:05 WiseWoman

 Typus Verschleierung Bearbeiter Hindemith Gesichtet
Untersuchte Arbeit:
Seite: 96, Zeilen: 2-20
Quelle: Borgatti_2002
Seite(n): 2, Zeilen: 1ff
When looking at visualizations of graphs such as Figure 3.1, it is important to realize that the only information contained in a diagram is adjacency; the position of nodes in a plane (and therefore the length of lines) is arbitrary unless otherwise specified. Hence it is usually dangerous to draw conclusions based on the spatial position of the nodes. For example, it is tempting to conclude that nodes in the middle of a diagram are more important than nodes on the peripheries, but this will often – if not usually – be a mistake.

When using graphs to represent terrorist networks, we typically use each line to represent instances of the same social relation, so that if (a, b) indicates a friendship between a person located at node a, and a person located at node b, then (d, e) indicates a friendship between d and e. Thus, each distinct social relation that is empirically measured on the same group of people is represented by separate graphs, which are likely to have different structures (after all, who talks to whom, is not the same as who dislikes whom).

The natural graphical representation of an adjacency matrix is a [table, such as shown in Figure 3. 2.]

When looking at visualizations of graphs such as Figure 1, it is important to realize that the only information contained in the diagram is adjacency; the position of nodes in the plane (and therefore the length of lines) is arbitrary unless otherwise specified. Hence it is usually dangerous to draw conclusions based on the spatial position of the nodes. For example, it is tempting to conclude that nodes in the middle of a diagram are more important than nodes on the peripheries, but this will often – if not usually – be a mistake.

When used to represent social networks, we typically use each line to represent instances of the same social relation, so that if (a, b) indicates a friendship between the person located at node a and the person located at node b, then (d, e) indicates a friendship between d and e. Thus, each distinct social relation that is empirically measured on the same group of people is represented by separate graphs, which are likely to have different structures (after all, who talks to whom is not the same as who dislikes whom).

[...] The natural graphical representation of an adjacency matrix is a table, such as shown in Figure 2.

 Anmerkungen The source is not given. Note the slight adaptation to make the text fit the terrorist topic of the thesis. Sichter (Hindemith), WiseWoman

 Zuletzt bearbeitet: 2012-05-01 09:29:32 Hindemith

 Typus Verschleierung Bearbeiter Hindemith Gesichtet
Untersuchte Arbeit:
Seite: 97, Zeilen: 1-8
Quelle: Borgatti_2002
Seite(n): 2, Zeilen: 15ff
[The natural graphical representation of an adjacency matrix is a] table, such as shown in Figure 3. 2.

[TABLE, same as in source but extended by one row and one column]

Figure 3.2. Adjacency matrix for graph in Figure 3.1.

Examining either Figure 3.1 or Figure 3.2, we can see that not every vertex is adjacent to every other. A graph in which all vertices are adjacent to all others is said to be complete. The extent to which a graph is complete is indicated by its density, which is defined as the number of edges divided by the number possible. If self-loops are excluded, then the number possible is n(n-1)/2. Hence the density of the graph in Figure 3.1 is 7/21 = 0.33.

The natural graphical representation of an adjacency matrix is a table, such as

shown in Figure 2.

[TABLE]

Figure 2. Adjacency matrix for graph in Figure 1.

Examining either Figure 1 or Figure 2, we can see that not every vertex is adjacent to every other. A graph in which all vertices are adjacent to all others is said to be complete. The extent to which a graph is complete is indicated by its density, which is defined as the number of edges divided by the number possible. If self-loops are excluded, then the number possible is n(n-1)/2. [...] Hence the density of the graph in Figure 1 is 6/15 = 0.40.

 Anmerkungen The source is not given anywhere in the thesis. Sichter (Hindemith), Bummelchen

 Zuletzt bearbeitet: 2012-04-26 20:07:24 WiseWoman

 Typus KomplettPlagiat Bearbeiter Hindemith Gesichtet
Untersuchte Arbeit:
Seite: 98, Zeilen: 9-22
Quelle: Borgatti_2002
Seite(n): 3, Zeilen: 1ff
Similarly, any pair of vertices in which one vertex can reach the other via a sequence of adjacent vertices is called reachable. If we determine reachability for every pair of vertices, we can construct a reachability matrix R such as depicted in Figure 3.3. The matrix R can be thought of as the result of applying transitive closure to the adjacency matrix A.

[FIGURE, different from source]

Figure 3.3. Reachability matrix

A component of a graph is defined as a maximal subgraph in which a path exists from every node to every other (i.e., they are mutually reachable). The size of a component is defined as the number of nodes it contains. A connected graph has only one component.

A sequence of adjacent vertices $v_0, v_1, \ldots, v_n$ is known as a walk. A walk can also be seen as a sequence of incident edges, where two edges are said to be incident if they share exactly one vertex. A walk in which no vertex occurs more than once is known as a path.

Similarly, any pair of vertices in which one vertex can reach the other via a sequence of adjacent vertices is called reachable. If we determine reachability for every pair of vertices, we can construct a reachability matrix R such as depicted in Figure 3. The matrix R can be thought of as the result of applying transitive closure to the adjacency matrix A.

[FIGURE]

Figure 3

A component of a graph is defined as a maximal subgraph in which a path exists from every node to every other (i.e., they are mutually reachable). The size of a component is defined as the number of nodes it contains. A connected graph has only one component.

A sequence of adjacent vertices $v_0, v_1, \ldots, v_n$ is known as a walk. [...]. A walk can also be seen as a sequence of incident edges, where two edges are said to be incident if they share exactly one vertex. A walk in which no vertex occurs more than once is known as a path.

 Anmerkungen No source given. The table Nm gives (figure 3.3.) can be found in the source on page 4 (figure 4). Sichter (Hindemith), WiseWoman

 Zuletzt bearbeitet: 2012-04-26 20:13:16 WiseWoman

 Typus Verschleierung Bearbeiter Hindemith Gesichtet
Untersuchte Arbeit:
Seite: 99, Zeilen: 1-25
Quelle: Borgatti_2002
Seite(n): 3-4, Zeilen: p3: 13ff; p4: 1ff
A walk in which no edge occurs more than once is known as a trail. In Figure 3.1, the sequence a, b, c, e, d, c, g is a trail but not a path. Every path is a trail, and every trail is a walk. A walk is closed if $v_o = v_n$. A cycle can be defined as a closed path in which n >= 3. The sequence c, e, d in Figure 3.1 is a cycle. A tree is a connected graph that contains no cycles. In a tree, every pair of points is connected by a unique path. That is, a tree is a graph in which any two vertices are connected by exactly one path.

The length of a walk (and therefore a path or trail) is defined as the number of edges it contains. For example, in Figure 3.1, the path a, b, c, d, e has length 4. A walk between two vertices whose length is as short as any other walk connecting the same pair of vertices is called a geodesic. Of course, all geodesics are paths. Geodesics are not necessarily unique. From vertex a to vertex f in Figure 3.1, there are two geodesics: a, b, c, d, e, f and a, b, c, g, e, f.

The graph-theoretic distance (usually shortened to just “distance”) between two vertices is defined as the length of a geodesic that connects them. If we compute the distance between every pair of vertices, we can construct a distance matrix D such as depicted in Figure 3.3. The maximum distance in a graph defines the graph’s diameter. As shown in Figure 3.3, the diameter of the graph in Figure 3.1 is 4. If the graph is not connected, then there exist pairs of vertices that are not mutually reachable so that the distance between them is not defined and the diameter of such a graph is also not defined.

A walk in which no edge occurs more than once is known as a trail. In Figure 3, the sequence a, b, c, e, d, c, g is a trail but not a path. Every path is a trail, and every trail is a walk. A walk is closed if $v_o = v_n$. A cycle can be defined as a closed path in which n >= 3. The sequence c, e, d in Figure 3 is a cycle. A tree is a connected graph that contains no cycles. In a tree, every pair of points is connected by a unique path. That is, there is only one way to get from A to B.

The length of a walk (and therefore a path or trail) is defined as the number of edges it contains. For example, in Figure 3, the path a, b, c, d, e has length 4. A walk between twovertices whose length is as short as any other walk connecting the same pair of vertices iscalled a geodesic. Of course, all geodesics are paths. Geodesics are not necessarily unique. From vertex a to vertex f in Figure 1, there are two geodesics: a, b, c, d, e, f and a, b, c, g, e, f.

The graph-theoretic distance (usually shortened to just “distance”) between two vertices is defined as the length of a geodesic that connects them. If we compute the distance between every pair of vertices, we can construct a distance matrix D such as depicted in Figure 4. The maximum distance in a graph defines the graph’s diameter. As shown in [page 4] Figure 4, the diameter of the graph in Figure 1 is 4. If the graph is not connected, then there exist pairs of vertices that are not mutually reachable so that the distance between them is not defined and the diameter of such a graph is also not defined.

 Anmerkungen No source given, very minor adjustments Sichter (Hindemith), WiseWoman