SNA Chapter 1 Lecture 2

Representing a Network

• Adjacency matrix: A square matrix whose rows and columns represent the same set of nodes. Each entry indicates whether the corresponding nodes are connected. In a weighted network, the entry records the edge’s weight.
• Limitation of adjacency matrices: Large networks often have many unconnected node pairs, so their matrices contain mostly zeros. Storing all those entries can be inefficient.
• Adjacency list: Stores each node alongside its neighbors, omitting nonexistent connections. For weighted networks, the list can also record the weight of each connection. This provides a more compact representation for sparse networks.

Network Types by Links and Nodes

• Unipartite network: A single, undivided set of nodes, with no partition-based restriction on which nodes may connect.
• Bipartite network: Nodes are divided into two partitions. Connections run across the partitions, not between nodes within the same partition. For example, users can connect to items they purchase. The same principle can extend to networks with more than two partitions.
• Signed network: Edges carry signs, such as positive or negative, to distinguish relationships—for example, friendship versus hostility, or a paper praising versus criticizing another paper.
• Homogeneous network: Nodes are all of the same type, and edges represent the same type of relationship, such as users connected by follower links.
• Heterogeneous network: Includes different node types, edge types, or both. For example, a network may contain users and posts, with different relationships connecting them.
• Attributed network: Nodes and/or edges have additional properties, or attributes. Such information can help with tasks like predicting or recommending future links.
• Multidimensional network: Represents different kinds of relationships in separate layers. For instance, one layer might show follower relationships and another retweets. Each layer can be homogeneous even if the combined network contains multiple relation types.

Local and Temporal Views

• Egocentric network: A local view centered on a particular node.
  • The central node is the ego.
  • Its immediate, one-hop neighbors are the alters.
  • The network includes the ego, its alters, and the induced subgraph: all original-network edges connecting any of those included nodes.
• Static network: Represents the network without incorporating time, either because time information is unavailable or because it is ignored.
• Temporal network: Tracks how the network changes over time, such as nodes or edges being added or removed. It can be viewed through snapshots at different timestamps. Tracking the behavior of many entities over time can be difficult, but temporal data can support analyses of network activity and applications.

Hypergraphs

A hypergraph generalizes an ordinary graph. In a conventional graph, each edge connects two nodes; in a hypergraph, a hyperedge can connect multiple nodes at once. For example, a research paper can be represented as a hyperedge connecting all of its authors. Two papers’ hyperedges overlap when they share an author.

Speakers and Sources Featured

• Speaker: One unnamed lecturer presenting the material.
• Other audio: Introductory and closing music.