Dear Wiki user,
You have subscribed to a wiki page or wiki category on "Hama Wiki" for change notification.
The "GraphAndMatrices" page has been changed by udanax.
http://wiki.apache.org/hama/GraphAndMatrices?action=diff&rev1=7&rev2=8

 == Graphs ==
+ * See [[GraphPackage Hama Graph Computing Framework]]
 A graph G(V,E) is a set of vertices (V) together with a set of edges (E). Some synonyms:

 <rowbgcolor="#ececec"> VerticesEdges
 <bgcolor="#ececec">Mathematicsnode, pointline, arc, link
 <bgcolor="#ececec">Sociologyactor, agenttie

 There are several crosscutting 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 nonsymmetric 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 NonValued
 * In nonvalued 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 NonReflexive
 * Reflexive graphs allow selfloops. 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.
 * Multigraphs
 * 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, 1mode actor by actor matrix like this:

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



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

