Topic 4: Graph Theory Flashcards
(26 cards)
Types of Graphs
- Undirected Graphs: Mutual connections e.g. Facebook friends
- Directed Graphs: One-way connections e.g. Twitter followers
- Weighted Graphs: Quantifies connection strength e.g. Message frequency
Connected Graph
Every node can be reached by every other node
Strongly Connected Component
A tightly linked subset of nodes where every node is reachable from every other node via directed paths e.g. a friendship group or interest-based community
Bridge
A edge that, if removed, would disconnect parts of the network and reduce reach and communication
Local Bridge Span
quantifies the value of a an edge as the distance between the two connected nodes if the bridge were deleted
Complete Graph
Every pair of nodes is directly connected (maximum connectivity)
Degree Centrality
Measures the importance of a node through the number of edges connected to it
In-degree
The number of incoming edges to a node, indicating a node’s popularity/importance
Out-degree
The number of outgoing links from a node, indicating a node’s authority/engagement, for example
- Citing many papers indicates the node is a well-referenced experts
- Following many social media accounts indicates the node is active and engaged
Network Scale
A characteristic size that defines the system, such as the average degree per node
E.g. A road network, where nodes are intersections, has a scale of around 3 to 5
Scale-free Networks
Follow a power-law degree distribution, they have no characteristic scale and are robust against accidental failure but vulnerable to attacks on hubs
Scale-free Networks on the Web
- Social Networks: Few users have many followers
- Web Links: Few sites get most traffic
- Citations: Few papers are cited extensively
How do Scale-free Networks Grow?
Preferential Attachment: where nodes are more likely to connect to existing nodes with higher degrees, forming hubs
Betweenness Centrality
Measures the importance of a node or edge through the number of shortest paths between other nodes that pass through it. Identifies key influences, brokers, and checkpoints
Bridges have a relatively high betweenness centrality
Closeness Centrality
Measures how quickly a node can reach all other nodes in a network
High-closeness nodes are not necessarily hubs but are well positioned
Eigenvector Centrality
Measures importance based on the importance of its connections i.e. quality over quantity
Local Clustering Coefficient
An indication of how well-connected a node’s neighbours are
Divisive Partitioning Algorithm
An approach to dividing a graph by iteratively dividing into smaller subsets until a specific criteria is met
Agglomerative Partitioning Algorithm
An approach to dividing a graph by starting with individual nodes and progressively merging them into larger clusters based on predefined criteria to form cohesive groups
Triadic Closure
If two people have a mutual friend, there is an increase likelihood that they will become friends themselves.
Forms triangles in the graph, contributing to network clostering
Strong Triadic Closure
A node satisfies strong triadic closure if it has strong ties to two other nodes and there is at least a weak tie between those two nodes
Requirements for a Balanced 3-Node Cycle in a Signed Graph
- All Three Edges Are Positive: A friend of a friend of a friend
- OR, Two Edges are Negative, One is Positive: Enemy of my enemy is my friend
The Balance Theorem
A signed complete graph is balanced if either
1. All pairs of nodes are friends
2. OR, the nodes can be divided into two groups such that
- Each pair of people in group 1 likes each other
- Each pair of people in group 2 likes each other
- Everyone in group 1 is an enemy of everyone in group 2
Social Capital
The resources and benefits accessible by an individual through their social network
