Quelle:Nm/Borgatti 2002
< Quelle:Nm
diesem Wiki
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  6 
[1.] Nm/Fragment 095 12  Diskussion Zuletzt bearbeitet: 20120426 19:55:43 WiseWoman  Borgatti 2002, Fragment, Gesichtet, KomplettPlagiat, Nm, SMWFragment, Schutzlevel sysop 


Untersuchte Arbeit: Seite: 95, Zeilen: 1215  Quelle: Borgatti_2002 Seite(n): 1, Zeilen: 810 

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. 
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/ 

[2.] Nm/Fragment 096 02  Diskussion Zuletzt bearbeitet: 20120426 19:43:05 WiseWoman  Borgatti 2002, Fragment, Gesichtet, Nm, SMWFragment, Schutzlevel sysop, Verschleierung 


Untersuchte Arbeit: Seite: 96, Zeilen: 220  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. 
The source is not given. Note the slight adaptation to make the text fit the terrorist topic of the thesis. 

[3.] Nm/Fragment 097 01  Diskussion Zuletzt bearbeitet: 20120501 09:29:32 Hindemith  Borgatti 2002, Fragment, Gesichtet, Nm, SMWFragment, Schutzlevel sysop, Verschleierung 


Untersuchte Arbeit: Seite: 97, Zeilen: 18  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 selfloops are excluded, then the number possible is n(n1)/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 selfloops are excluded, then the number possible is n(n1)/2. [...] Hence the density of the graph in Figure 1 is 6/15 = 0.40. 
The source is not given anywhere in the thesis. 

[4.] Nm/Fragment 098 09  Diskussion Zuletzt bearbeitet: 20120426 20:07:24 WiseWoman  Borgatti 2002, Fragment, Gesichtet, KomplettPlagiat, Nm, SMWFragment, Schutzlevel sysop 


Untersuchte Arbeit: Seite: 98, Zeilen: 922  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 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 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. 
No source given. The table Nm gives (figure 3.3.) can be found in the source on page 4 (figure 4). 

[5.] Nm/Fragment 099 01  Diskussion Zuletzt bearbeitet: 20120426 20:13:16 WiseWoman  Borgatti 2002, Fragment, Gesichtet, Nm, SMWFragment, Schutzlevel sysop, Verschleierung 


Untersuchte Arbeit: Seite: 99, Zeilen: 125  Quelle: Borgatti_2002 Seite(n): 34, 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 . 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 graphtheoretic 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 . 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 graphtheoretic 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. 
No source given, very minor adjustments 
