Network Science and Game Theory Reference

Posted on May 20, 2026 in Business Administration and Management (BAM)

Graph Theory Fundamentals

Graph (G = (V, E)): A structure showing connections where V are nodes/vertices and E are edges/links.

  • Node/Vertex: The object (e.g., person, city, website).
  • Edge: The connection (e.g., friendship, road, hyperlink).
  • Directed Edge: Has an arrow; order matters (A points to B).
  • Undirected Edge: No arrow; order does not matter.

Paths and Connectivity

  • Path: A route between nodes; length is the number of edges.
  • Simple Path: No repeated nodes.
  • Walk: Repeats allowed.
  • Cycle: Starts and ends at the same node.
  • Connected Graph: Every node can reach every other node.
  • Component: A separate connected group.
  • Degree: Number of edges touching a node.
  • Hub: A high-degree node.
  • Giant Component: A large component, usually at least n/2 nodes.

Algorithms and Theorems

  • BFS: Finds shortest paths in unweighted graphs.
  • Handshaking Theorem: Total degrees = 2 × edges.
  • Odd Degree Rule: The number of odd-degree nodes must be even.
  • Random Graph G(n, p): n nodes, p probability of edge existence.
  • Connectivity Threshold: Around p = ln(n)/n.

Strong and Weak Ties

  • Strong Tie: Close friend.
  • Weak Tie: Acquaintance; useful for new information.
  • Triadic Closure: If A knows B and C, B and C are likely to connect.
  • Clustering Coefficient: CC(A) = actual edges among A’s friends / possible edges.
  • Local Bridge: Edge whose endpoints have no shared neighbors.
  • Bridge: Removing the edge disconnects the graph.
  • Strong Triadic Closure: If A has strong ties to B and C, B and C must be connected.
  • Neighborhood Overlap: Common neighbors / total neighbors.
  • Betweenness: Measures how many shortest paths use an edge.

Network Context and Homophily

  • Homophily: Tendency to connect with similar people.
  • Affiliation Network: Bipartite graph connecting people to foci (activities/groups).
  • Closure Types:
    • Triadic: Shared friend creates friendship.
    • Focal: Shared activity creates friendship.
    • Membership: Friend causes someone to join an activity.

Positive and Negative Relationships

  • Structural Balance: A signed graph is balanced if every triangle is balanced.
  • Balanced Triangles: +++ and +−− are balanced; ++− and −−− are not.
  • Balance Theorem: A balanced complete graph splits into two groups where edges inside are + and between are −.
  • Odd Negative Cycle Rule: If a cycle has an odd number of negative edges, it is not balanced.

Game Theory

  • Nash Equilibrium: Players choose best responses to each other; nobody wants to switch alone.
  • Dominant Strategy: Best response regardless of the other player’s move.
  • Prisoner’s Dilemma: Selfish choices lead to a worse outcome for both.
  • Coordination Game: Players benefit from choosing the same option.
  • Zero-Sum Game: One player’s gain is the other’s loss.
  • Mixed Strategy: Randomizing choices when no pure Nash equilibrium exists.

Traffic and Auctions

  • Braess’s Paradox: Adding a new road can increase travel time at equilibrium.
  • Second-Price Auction: Truthful bidding (bid = true value) is the dominant strategy.
  • First-Price Auction: Bid shading (bidding below true value) is standard.

Matching Markets

  • Perfect Matching: Everyone on one side is matched to exactly one node on the other.
  • Constricted Set: A group with more people than available neighbors; prevents perfect matching.
  • Market-Clearing Prices: Prices where the preferred-seller graph has a perfect matching.

Web and Information Networks

  • Bow-Tie Structure: SCC core, IN pages, OUT pages, and tendrils.
  • HITS: Hubs (good lists) and Authorities (good answers).
  • PageRank: Measures importance by flowing score through links; scaled version prevents leakage.

Information Cascades

  • Information Cascade: Individuals ignore private information to follow the crowd.
  • Bayes’ Rule: Used to update beliefs based on new evidence.
  • Fragility: Cascades can be broken by new, real information.

Cascading Behavior

  • Threshold Rule: Node switches to behavior A if fraction of neighbors using A ≥ q = b / (a + b).
  • Clusters: Dense groups can block cascades.
  • Small-World Phenomenon: Short paths exist in large networks due to weak-tie shortcuts.