Samenvatting
Summary Network and Graphs
- Instelling
- Vrije Universiteit Amsterdam (VU)
Samenvatting van alle colleges
[Meer zien]Voorbeeld 4 van de 24 pagina's
Voorbeeld 4 van de 24 pagina's
In winkelwagengesponsord bericht van onze partner
1 beoordeling
Door: paulogeusau • 6 jaar geleden
Voorbeeld van de inhoud
Network and GraphsContents
Lectures..............................................................................................................................................3
1. Introduction .............................................................................................................................. 3
2. Foundations .............................................................................................................................. 4
Formalities .................................................................................................................................4
Graph representations ...............................................................................................................4
Connectivity ...............................................................................................................................5
Drawing graphs ..........................................................................................................................6
3. Extensions ................................................................................................................................. 7
Directed graphs ..........................................................................................................................7
Weighted graphs ........................................................................................................................8
Colorings ....................................................................................................................................8
4. Network Travels ...................................................................................................................... 10
Euler tours ............................................................................................................................... 10
Hamilton cycles ....................................................................................................................... 11
5. Trees........................................................................................................................................ 12
Background & Fundamentals .................................................................................................. 12
Spanning trees ........................................................................................................................ 13
Routing in communication networks...................................................................................... 13
6. Network Analysis .................................................................................................................... 15
Vertex degree.......................................................................................................................... 15
Distance statistics ................................................................................................................... 15
Clustering coefficients............................................................................................................. 15
Centrality................................................................................................................................. 16
7. Random Networks .................................................................................................................. 17
Introduction ............................................................................................................................ 17
Classical random networks ..................................................................................................... 17
Small worlds ............................................................................................................................ 18
Scale-free networks ................................................................................................................ 19
9. Social Networks....................................................................................................................... 22
Introduction ............................................................................................................................ 22
Sociograms .............................................................................................................................. 22
1
,Basic concepts ......................................................................................................................... 22
Affiliation networks................................................................................................................. 24
2
,Lectures
1. Introduction
Many real-world systems can be viewed as a collection of nodes that are linked to each other.
When it comes to connecting people, there is a long history of networks:
• In the very old days: carriers of messages (pigeons, ponies, etc.)
• Also in the old days: fire beacons, mirrors, drums, flags.
We need encoding schemes to use this type of communication.
• Since the late 1900s: communication networks.
physical connection between the two parties ⇒ circuit-switched network. In modern telephony
In traditional telecommunications networks, to hold a conversation, it was necessary to make a
networks, everything is packetized:
• Data (including samples from continuous media) is put into a packet.
• Packets are extended with address of destination and are independently routed.
Connect many computers through switches that automatically discover and maintain routes. The
Internet was born.
3
, 2. Foundations
Formalities
Graph: definition
A graph G is a tuple , of vertices V and a collection of edges E. Each edge ∈ is said to
connect two vertices , ∈ and is denoted as = 〈 , 〉. Notations:
The complement Ḡ of a graph G, has the same vertex set as G, but ∈ ̅
, .
∉
if and only if
For any graph G and vertex ∈
.
, the neighbor set N(v) of v is the set of vertices (other than
= ∈ | ≠ ,〈 , 〉 ∈ }
v) adjacent to v:
Vertex degree
The number of edges incident with a vertex v is called the degree of v, denoted as δ(v). Loops,
i.e., edges joining a vertex with itself, are counted twice. For all graphs G:
= ∗ | |
∈
Proof: When we count the edges of a graph G by enumerating the edges incident with each vertex of
G, we are counting each edge exactly twice.
Degree sequence
An (ordered) degree sequence is an (ordered) list of the degrees of the vertices of a graph. A
degree sequence is graphic if there is a (simple) graph with that sequence.
An ordered degree sequence s = [k, d1, d2, …, dn-1] is graphic, if and only if s* = [d1-1, d2-1, …, dk-1,
dk+1-1, …, dn-1] is also graphic. (We assume k ≥ di ≥ di+1).
Length s = n, but length s* = n - 1.
Consider a graph with sequence [4, 4, 3, 3, 3, 3, 2, 2]. Let δ(u) = 4 and consider V = {v1, v2, v3, v4}
as next highest degrees and W = {w1, w2, w3} the rest. If u is not connected only to vertices from V,
then distracting a degree from the highest nodes will not result in the correct sequence of the
resulting graph.
Problem: u is linked to a w but not to a vj, with δ(w) < δ (vj). But because δ(w) < δ (vj), there
Solution: Remove 〈 , 〉 and 〈 ! , "〉. Add 〈", 〉 and 〈 , ! 〉.
exists x adjacent to vj but not to w.
Subgraphs
# ⊆ and # ⊆ such that for all ∈ # with
〈 〉
= , ∶ , ∈ # .
H is a subgraph of G if
The subgraph induced by ∗ ⊆ has vertex set V* and edge set 〈 , 〉 ∈ | , ∈ }.
Denoted as # = & ∗ '. The subgraph induced by ∗ ⊆
Denoted as # = & ∗ '.
has vertex set V(G) and edge set E*.
Graph representations
Adjacency matrix
Adjacency matrix is symmetric: A[i, j] = A[j, i]. G is simple ⇔ A[i, j] ≤ 1 and A[i, i] = 0.
.
∀ *: ,&*, -' = *
-/0
4
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper BobotieBush. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €2,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 53068 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen