NETS 1500 Midterm

a representation of a graph in which each node has a list of nodes that are adjacent to it, i.e. connected to it by an edge

rows are origin node, columns are "to" node. 1 if the nodes are adjacent

bipartite graph

- file layer (FTP)
- email (SMTP, POP, IMAP)
- DNS (domain name system; name -> IP Address)

Graph G that has a shortest path from node A to B. For shortest path, 1 unit of "flow" goes along all the edges

- if k shortest paths, each path gets 1/kth flow
- total amount of flow carried by an edge (# of shortest paths that this edge is a part of)

consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set

an edge is a bridge if deleting the edge makes the graph not connected

a clique of size k is a graph with k nodes where each node has edges to all the other nodes

the probability that two randomly selected friends of a node A are friends with each other

A set of nodes in a graph such that every node in the set has a path to every other node in the set and does not have a path to any node outside the set

path such that start node and end node are the same

the number of edges that meet at a vertex

A diagram consisting of vertices, joined by directed edges.

- reverse hierarchical lookup

connects two nodes

the tendency that two people will form a link when two people share the same interests.

sets of nodes at the same distance from the source of the BFS

way of representing relationships that exist between pairs of objects

- birds of a feather flock together
- we tend to be similar to our friends

test:
- compare cross-edges (reality) to expectation (2pq)
- reality is a lot less than 2pq ==> homophily
- p is proportion red, q is proportion blue

The number of neighbours for that vertex.

- host addressing & ID
- best effort packet delivery
- protocol = set of guidelines

- IPv$
- 32bit address

- physical media (wifi, cable ==> coax, fibre optic)
- bits and checksums

1. an edge where the end points don't have a common friend, OR
2. deleting the edge would increase the distance (shortest path) to a value strictly grater than 2

- weak tiesf

if two nodes (A, B) are connected and A is also connected to a certain focus C, B is likely to also become connected to C.

for an edge A-B

"more gradation than strong/weak"

number of nodes that are neighbors of both A & B divided y nodes that are neighbors of either A or B

the number of edges going out from the vertex

sequence of alternating nodes and edges that starts at a node and ends at a node, such that each edge is incident on the predecessor and successor node

A series of social relationships that links a person directly to others, and through them indirectly to still more people.

distance between the nodes if the edge were deleted

close friend

a node A violates STC if it has
1. strong tie to two other nodes B & C, and
2. there is no edge at all (weak or strong) between B and C.

satisfies STC if it does not violate it

given a DAG, an ordering of vertices such that if edge (u,v) exists, u must come before v in the ordering

- connection-oriented
- reliable packet delivery
- slow
- email, messages, chat, canvas quiz submissions, uploading content, banking, finance, shopping carts

- segmentation
- congestion/flow control
- error control
- application addressing (end to end message transfer)

if two people in a social network have a friend in common, then there is an increased likelihood that they will become friends themselves at some point in the future

A graph in which the edges have no direction

- connectionless
- no reliability guarantees
- fast
- video chat, voice chat, streaming, DNS

a node in a graph

acquaintance

can be positive or negative, can be helpful in calculating path cost