Page History

Graphs

A graph G(V,E) is a set of vertices (V) together with a set of edges (E). Some synonyms:

There are several cross-cutting dimensions that distinguish among graphs.

• Directed vs Undirected:
  • Directed graphs (also called digraphs) consist of ordered pairs. The links in a directed graph are called arcs. Can use these to represent non-symmetric relations like "is the boss of" or "is attracted to"
  • Undirected graphs (also known simply as "graphs") consist of unordered pairs. They are used for the relations which are necessarily symmetric, such as "is the sibling of" or "lives with"
• Valued vs Non-Valued
  • In non-valued graphs, nodes are either connected or not. Either Sally and Bill are siblings, or they're not.
  • In valued graphs, the lines have values attached to represent characteristics of the relationships, such as strength, duration, capacity, flow, etc.
• Reflexive vs Non-Reflexive
  • Reflexive graphs allow self-loops. That is, a node can have a tie to itself. This is mostly useful when the nodes are collectivities. For example, if the nodes are cities and the ties represent phonecalls between people living in those cities, it is possible (a virtual certainty) that there will be ties from a city to itself.
• Multi-graphs
  • If more than one edge connects two vertices, this is a multigraph. In general, we do not use multigraphs, preferring to use either valued graphs (to represent the number of interactions between A and B) or wholly separate graphs (to represent substantively different relations, such as "does business with" and "is married to"
    

Matrices

We can record who is connected to whom on a given social relation via an adjacency matrix. The adjacency matrix is a square, 1-mode actor by actor matrix like this:

If the matrix as a whole is called X, then the contents of any given cell are denoted x_ij. For example, in the matrix above, x_ij = 1, because A likes B. Note that this matrix is not quite symmetric (x_ij not always equal to x_ji).

Anything we can represent as a graph, we can also represent as a matrix. For example, if it is a valued graph, then the matrix contains the values instead of 0s and 1s.

By convention, we normally record the data so that the row person "does it to" the column person. For example, if the relation is "gives advice to", then x_ij = 1 means that person i gives advice to person j, rather than the other way around. However, if the data not entered that way and we wish it to be so, we can simply transpose the matrix. The transpose of a matrix X is denoted X'. The transpose simply interchanges the rows with the columns.

Matrix Algebra

...

• See Hama Graph Computing Framework