hama-commits mailing list archives

Site index · List index
Message view
Top
From Apache Wiki <wikidi...@apache.org>
Subject [Hama Wiki] Update of "GraphAndMatrices" by udanax
Date Thu, 06 Nov 2008 13:51:47 GMT
```Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Hama Wiki" for change notification.

The following page has been changed by udanax:
http://wiki.apache.org/hama/GraphAndMatrices

------------------------------------------------------------------------------
+ == Graphs ==
+
+ A graph G(V,E) is a set of vertices (V) together with a set of edges (E). Some synonyms:
+
+ ||<rowbgcolor="#ececec"> ||Vertices||Edges||
+ ||<bgcolor="#ececec">Sociology||actor, agent||tie||
+
+ 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 matrix like this:

- ||   || A || B || C || D || E || F || G ||<|8>[http://wiki.apache.org/hama-data/attachments/BigTableForGmail/attachments/graph.jpg]||
+ ||<rowbgcolor="#ececec"> || A || B || C || D || E || F || G ||<|8>[http://wiki.apache.org/hama-data/attachments/GraphAndMatrices/attachments/graph.jpg]||
- || A ||   || 1 || 0 || 1 || 0 || 0 || 1 ||
+ ||<bgcolor="#ececec"> A ||   || 1 || 0 || 1 || 0 || 0 || 1 ||
- || B || 1 ||   || 1 || 0 || 1 || 0 || 0 ||
+ ||<bgcolor="#ececec"> B || 1 ||   || 1 || 0 || 1 || 0 || 0 ||
- || C || 1 || 1 ||   || 1 || 1 || 0 || 0 ||
+ ||<bgcolor="#ececec"> C || 1 || 1 ||   || 1 || 1 || 0 || 0 ||
- || D || 1 || 1 || 1 ||   || 0 || 0 || 0 ||
+ ||<bgcolor="#ececec"> D || 1 || 1 || 1 ||   || 0 || 0 || 0 ||
- || E || 0 || 0 || 0 || 1 ||   || 1 || 0 ||
+ ||<bgcolor="#ececec"> E || 0 || 0 || 0 || 1 ||   || 1 || 0 ||
- || F || 0 || 0 || 0 || 0 || 1 ||   || 0 ||
+ ||<bgcolor="#ececec"> F || 0 || 0 || 0 || 0 || 1 ||   || 0 ||
- || G || 1 || 1 || 0 || 0 || 0 || 0 ||   ||
+ ||<bgcolor="#ececec"> G || 1 || 1 || 0 || 0 || 0 || 0 ||   ||

@@ -20, +41 @@

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 [:Architecture: Hama Architecture & Overview]
+

```
Mime
View raw message