Summary
Summary Network and Graphs
- Course
- Institution
Summary of all colleges
[Show more]
1 review
By: paulogeusau • 6 year ago
Seller
Follow
BobotieBush
Reviews received
Content preview
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller BobotieBush. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.23. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67163 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now