Network Analysis with igraph |
---|

This section introduces the igraph data model. It is recommended that the reader should be familiar with this model of computation to understand the semantics of the igraph functions better.

An igraph graph is either *directed* or
*undirected*, igraph cannot handle mixed graphs
with both directed and undirected edges.

The igraph data model is slightly different for directed and
undirected graphs, we start with the directed case. In igraph
vertices are identified by *vertex id*s: integer
number between zero and |V|-1, if |V| is the number of vertices in the
graph. Thus the numbering of vertex ids is always continual, all
igraph operations on graphs keep this important property.

Directed igraph edges are ordered pairs or vertex ids. A directed graph is an ordered multiset of directed edges and some additional meta data: the number of vertices in the graph and a boolean tag to mark the graph as directed. Here is an example of a directed igraph graph:

( vertices: 6, directed: yes, ( (0,2), (2,2), (2,3), (3,3), (3,4), (3,4), (4,1) ) )

Just like the vertices have vertex ids, igraph edges also have ids: edge ids are integer numbers between zero and |E|-1, |E| is the number of edges in the graph.

An undirected igraph edge is a two-element or one-element set of vertex ids. The two element set is a non-loop edge, ie. the edge connects different vertices, while loop edges are represented with a single-element set. An undirected graph is an ordered multiset of undirected edges, plus the usual meta data: the number of vertices and the fact that the graph is undirected. Here is an example for an undirected graph:

( vertices: 6, directed: no, ( {0,2}, {2}, {2,3}, {3}, {3,4}, {3,4}, {4,1} ) )

This graph contains both loop edges ({2} and {3}, ie. (2-2) and (3-3)) and multiple edges ({3,4} twice).

We give some simple examples on how this data model is used in
computations. The first example is the
`are.connected()`

function, this decides whether two
vertices are connected by an edge. Lets assume that G1 and G2 are the
graphs from the previous two sections, G1 is the directed, G2 the
undirected graph. Now if we check with
`are.connected()`

whether vertices 0 and 2 are
connectedin G1, the function searches for the (0,2) *directed
pair*, and since it finds it it returns positive result. If the
same search is performed on G2, the function searches for the {0,2}
set and the result is, again, positive. Now it is perhaps obvious by
now that if we suppply the vertices in the opposite order, ie. 2 and 0
then in G1 the (2,0) ordered pair is requested, so the answer is
negative. For G2 {0,2}={2,0} is searched again, the answer is still
positive.

Another simple example is the `neighbors()`

command,
this can be used to find the neighboring vertices of a
vertex. `neighbors()`

(like many other functions in
igraph) has a parameter called * mode*. This
parameter defines how the search is performed in directed graphs. Let
us assume that we are interested in the neighbors of vertex 3. If

`mode`

`out`

then the
graph's edge list (which is a multiset) is searched for elements
having 3 in the first position of the ordered pair and returns the
vertex ids in the second position in these elements. So the answer is
(3,4,4). Now if `mode`

`in`

then the role of the first and second positions is exchanged and
(2,3) is returned. The third possible value of
`mode`

`all`

, in this case
pairs having 3 at either at the first or second positions are searched
and the
The * mode* argument is always ignored when
dealing with undirected graphs, as these graphs store an edge as an
unordered pair (ie. a set). For example running

`neighbors()`

on graph G2 and vertex 3, the result is
(2,3,4,4).
Note that if we set * mode* to

`all`

on a directed graph that essentially means
that we use the corresponding undirected graph for calculation. Also
note that the corresponding undirected graph always have the same
number of edges as the directed counterpart, eg. if the directed graph
contains (3,4) and (4,3) these edges make two {3,4} edges in the
undirected graph.
Some igraph functions have a * mode* for other
purposes: eg.

`graph.tree()`

and
`graph.star()`

.
<< Installation |
Graphs Objects >> |