incubator-hama-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Hama Wiki] Trivial Update of "GraphAndMatrices" by udanax
Date Wed, 02 Dec 2009 08:01:45 GMT
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"> ||Vertices||Edges||
- ||<bgcolor="#ececec">Mathematics||node, point||line, arc, link||
- ||<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 actor by actor matrix like this:
- 
- ||<rowbgcolor="#ececec"> || A || B || C || D || E || F || G ||<|8>[[http://wiki.apache.org/hama-data/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]]
- 

Mime
View raw message