Safe Haskell  None 

 Basic types
 Pure Haskell functions
 Chapter 11. Vertex and Edge Selectors and Sequences, Iterators
 Chapter 13. Structural Properties of Graphs
 13.1 Basic properties
 13.2 Shortest Path Related Functions
 13.4 Graph Components
 13.5 Centrality Measures
 13.6 Estimating Centrality Measures
 13.7 Centralization
 13.8 Similarity Measures
 13.9 Spanning Tress
 13.10 Transitivity or Clustering Coefficient
 13.12 Spectral properties
 13.14 Mixing patterns
 13.15 KCores
 13.16 Topological sorting, directed acyclic graphs
 13.17 Maximum cardinality search, graph decomposition, chordal graphs
Haskell bindings to the igraph C library.
Function descriptions have been copied from http://igraph.sourceforge.net/doc/html/index.html from the specified sections.
 data Graph d a where
 data D
 data U
 class IsUnweighted d
 class (Eq a, Hashable a, Eq (Edge d a), Hashable (Edge d a)) => E d a where
 data Weighted d
 toEdgeWeighted :: E d a => a > a > Int > Edge (Weighted d) a
 getWeight :: Edge (Weighted d) a > Int
 class IsUndirected u where
 type ToDirected u
 class IsDirected d where
 type ToUndirected d
 emptyGraph :: E d a => Graph d a
 fromList :: E d a => [(a, a)] > Graph d a
 fromListWeighted :: (E d a, IsUnweighted d) => [(a, a, Int)] > Graph (Weighted d) a
 insertEdge :: Edge d a > Graph d a > Graph d a
 deleteEdge :: Edge d a > Graph d a > Graph d a
 deleteNode :: a > Graph d a > Graph d a
 reverseGraphDirection :: Graph d a > Graph d a
 toDirected :: (IsUndirected u, E (ToDirected u) a) => Graph u a > Graph (ToDirected u) a
 toUndirected :: (IsDirected d, E (ToUndirected d) a) => Graph d a > Graph (ToUndirected d) a
 numberOfNodes :: Graph d a > Int
 numberOfEdges :: Graph d a > Int
 member :: a > Graph d a > Bool
 nodes :: Graph d a > [a]
 edges :: Graph d a > [Edge d a]
 neighbours :: a > Graph d a > [a]
 data VertexSelector a
 vsSize :: Graph d a > VertexSelector a > Int
 selectedVertices :: Graph d a > VertexSelector a > [a]
 data EdgeSelector d a
 = EsAll
  EsNone
  EsIncident a
  EsSeq a a
  EsFromTo (VertexSelector a) (VertexSelector a)
  Es1 (Edge d a)
  EsList [Edge d a]
 esSize :: Graph d a > EdgeSelector d a > Int
 selectedEdges :: Graph d a > EdgeSelector d a > [Edge d a]
 areConnected :: Graph d a > a > a > Bool
 shortestPaths :: (Ord a, Hashable a) => Graph d a > VertexSelector a > VertexSelector a > Map (a, a) (Maybe Int)
 shortestPathsDijkstra :: (Ord a, Hashable a) => Graph (Weighted d) a > VertexSelector a > VertexSelector a > Map (a, a) (Maybe Int)
 shortestPathsBellmanFord :: (Ord a, Hashable a) => Graph (Weighted d) a > VertexSelector a > VertexSelector a > Map (a, a) (Maybe Int)
 shortestPathsJohnson :: (Ord a, Hashable a) => Graph (Weighted d) a > VertexSelector a > VertexSelector a > Map (a, a) (Maybe Int)
 getShortestPaths :: Graph d a > a > VertexSelector a > [([a], [Edge d a])]
 getShortestPathsDijkstra :: Graph (Weighted d) a > a > VertexSelector a > [([a], [Edge (Weighted d) a])]
 getShortestPath :: Graph d a > a > a > ([a], [Edge d a])
 getShortestPathDijkstra :: Graph (Weighted d) a > a > a > ([a], [Edge (Weighted d) a])
 getAllShortestPaths :: Graph d a > a > VertexSelector a > [[a]]
 getAllShortestPathsDijkstra :: Graph (Weighted d) a > a > VertexSelector a > [[a]]
 averagePathLength :: Graph d a > Bool > Bool > Double
 pathLengthHist :: Graph d a > Bool > ([Double], Double)
 diameter :: Graph d a > Bool > Bool > (Int, (a, a), [a])
 diameterDijkstra :: Graph d a > (Double, a, a, [a])
 girth :: Graph d a > (Int, [a])
 eccentricity :: Graph d a > VertexSelector a > [(a, Int)]
 radius :: Graph d a > Int
 subcomponent :: Graph d a > a > [a]
 inducedSubgraph :: Graph d a > VertexSelector a > SubgraphImplementation > Graph d a
 data SubgraphImplementation
 subgraphEdges :: Graph d a > EdgeSelector d a > Graph d a
 clusters :: Graph d a > Connectedness > (Int, [Int])
 isConnected :: Graph d a > Connectedness > Bool
 decompose :: Graph d a > Connectedness > Int > Int > [Graph d a]
 data Connectedness
 biconnectedComponents :: Graph d a > (Int, [[Edge d a]], [[Edge d a]], [[a]], [a])
 articulationPoints :: Graph d a > [a]
 closeness :: Ord a => Graph d a > VertexSelector a > Map a Double
 betweenness :: Ord a => Graph d a > VertexSelector a > Map a Double
 edgeBetweenness :: Ord (Edge d a) => Graph d a > Map (Edge d a) Double
 pagerank :: Graph d a > VertexSelector a > Double > (Double, [(a, Double)])
 personalizedPagerank :: Graph d a > VertexSelector a > Double > (Double, [(a, Double)])
 personalizedPagerankVs :: Graph d a > VertexSelector a > Double > VertexSelector a > (Double, [(a, Double)])
 constraint :: Ord a => Graph d a > VertexSelector a > Map a Double
 maxdegree :: Graph d a > VertexSelector a > Bool > Int
 strength :: Ord a => Graph d a > VertexSelector a > Bool > Map a Int
 eigenvectorCentrality :: Graph d a > Bool > (Double, [(a, Double)])
 hubScore :: Graph d a > Bool > (Double, [(a, Double)])
 authorityScore :: Graph d a > Bool > (Double, [(a, Double)])
 closenessEstimate :: Ord a => Graph d a > VertexSelector a > Int > Map a Double
 betweennessEstimate :: Ord a => Graph d a > VertexSelector a > Int > Map a Double
 edgeBetweennessEstimate :: Ord (Edge d a) => Graph d a > Int > Map (Edge d a) Double
 centralizationDegree :: Ord a => Graph d a > Bool > Bool > (Map a Double, Double, Double)
 centralizationBetweenness :: Ord a => Graph d a > Bool > (Map a Double, Double, Double)
 centralizationCloseness :: Ord a => Graph d a > Bool > (Map a Double, Double, Double)
 centralizationEigenvectorCentrality :: Graph d a > Bool > Bool > (Double, Double, Double)
 centralizationDegreeTMax :: Either (Graph d a) Int > Bool > Double
 centralizationBetweennessTMax :: Either (Graph d a) Int > Double
 centralizationClosenessTMax :: Either (Graph d a) Int > Double
 centralizationEigenvectorCentralityTMax :: Either (Graph d a) Int > Bool > Bool > Double
 bibCoupling :: Graph d a > VertexSelector a > [(a, [(a, Int)])]
 cocitation :: Graph d a > VertexSelector a > [(a, [(a, Int)])]
 similarityJaccard :: Graph d a > VertexSelector a > Bool > [(a, [(a, Double)])]
 similarityJaccardPairs :: Graph d a > [Edge d a] > Bool > [(Edge d a, Double)]
 similarityJaccardEs :: Graph d a > EdgeSelector d a > Bool > [(Edge d a, Double)]
 similarityDice :: Graph d a > VertexSelector a > Bool > [(a, [(a, Double)])]
 similarityDicePairs :: Graph d a > [Edge d a] > Bool > [(Edge d a, Double)]
 similarityDiceEs :: Graph d a > EdgeSelector d a > Bool > [(Edge d a, Double)]
 similarityInverseLogWeighted :: Graph d a > VertexSelector a > [(a, [(a, Double)])]
 minimumSpanningTree :: Graph d a > [Edge d a]
 minimumSpanningTreeUnweighted :: IsUnweighted d => Graph d a > Graph d a
 minimumSpanningTreePrim :: IsUnweighted d => Graph (Weighted d) a > Graph (Weighted d) a
 transitivityUndirected :: Graph d a > Double
 transitivityLocalUndirected :: Graph d a > VertexSelector a > [(a, Double)]
 transitivityAvglocalUndirected :: Graph d a > Double
 transitivityBarrat :: Graph d a > VertexSelector a > [(a, Double)]
 laplacian :: Graph d a > Bool > [[Double]]
 assortativityNominal :: Eq vertexType => Graph d (vertexType, a) > Bool > Double
 assortativity :: (Eq vertexTypeIncoming, Eq vertexTypeOutgoing) => Graph d (vertexTypeIncoming, vertexTypeOutgoing, a) > Bool > Double
 assortativityDegree :: Graph d a > Bool > Double
 coreness :: Graph d a > [(Double, a)]
 isDAG :: Graph d a > Bool
 topologicalSorting :: Graph d a > [a]
 data FASAlgorithm
 = ExactIP
  ApproxEades
 feedbackArcSet :: Graph d a > FASAlgorithm > [a]
 maximumCardinalitySearch :: Graph d a > [(Int, a)]
 isChordal :: Graph d a > (Bool, [Edge d a])
Basic types
The internal graph representation wrapped into a GADT to carry around the
E d a
class constraint.
Directed graph
Undirected graph
class IsUnweighted d Source
class (Eq a, Hashable a, Eq (Edge d a), Hashable (Edge d a)) => E d a whereSource
Class for graph edges, particularly for undirected edges Edge U a
and
directed edges Edge D a
and weighted edges.
Weighted graphs, weight defaults to 0
IsUndirected (Weighted U)  
IsDirected (Weighted D)  
(E d a, IsUnweighted d) => E (Weighted d) a  
E d a => Eq (Edge (Weighted d) a)  
Eq (Edge d a) => Eq (Graph (Weighted d) a)  
(E d a, Ord (Edge d a)) => Ord (Edge (Weighted d) a)  
Show (Edge d a) => Show (Edge (Weighted d) a)  
Show (Edge d a) => Show (Graph (Weighted d) a)  
E d a => Hashable (Edge (Weighted d) a) 
Pure Haskell functions
These functions do not depend on the C library and perform no FFI calls.
Construction / modification
emptyGraph :: E d a => Graph d aSource
fromListWeighted :: (E d a, IsUnweighted d) => [(a, a, Int)] > Graph (Weighted d) aSource
insertEdge :: Edge d a > Graph d a > Graph d aSource
deleteEdge :: Edge d a > Graph d a > Graph d aSource
deleteNode :: a > Graph d a > Graph d aSource
reverseGraphDirection :: Graph d a > Graph d aSource
Reverse graph direction. This simply changes the associated
igraph_neimode_t
of the graph (IGRAPH_OUT
to IGRAPH_IN
, IGRAPH_IN
to
IGRAPH_OUT
, other to IGRAPH_OUT
). O(1)
toDirected :: (IsUndirected u, E (ToDirected u) a) => Graph u a > Graph (ToDirected u) aSource
toUndirected :: (IsDirected d, E (ToUndirected d) a) => Graph d a > Graph (ToUndirected d) aSource
Query
numberOfNodes :: Graph d a > IntSource
numberOfEdges :: Graph d a > IntSource
neighbours :: a > Graph d a > [a]Source
Chapter 11. Vertex and Edge Selectors and Sequences, Iterators
11.2 Vertex selector constructors
11.3 Generic vertex selector operations
vsSize :: Graph d a > VertexSelector a > IntSource
3.4. igraph_vs_size
— Returns the size of the vertex selector.
selectedVertices :: Graph d a > VertexSelector a > [a]Source
11.6 Edge selector constructors
data EdgeSelector d a Source
EsAll  
EsNone  
EsIncident a  
EsSeq a a  
EsFromTo (VertexSelector a) (VertexSelector a)  
Es1 (Edge d a)  
EsList [Edge d a] 
11.8 Generic edge selector operations
esSize :: Graph d a > EdgeSelector d a > IntSource
8.4. igraph_es_size
— Returns the size of the edge selector.
selectedEdges :: Graph d a > EdgeSelector d a > [Edge d a]Source
Chapter 13. Structural Properties of Graphs
13.1 Basic properties
areConnected :: Graph d a > a > a > BoolSource
1.1. igraph_are_connected
— Decides whether two vertices are connected
13.2 Shortest Path Related Functions
shortestPaths :: (Ord a, Hashable a) => Graph d a > VertexSelector a > VertexSelector a > Map (a, a) (Maybe Int)Source
2.1. igraph_shortest_paths
— The length of the shortest paths between
vertices.
shortestPathsDijkstra :: (Ord a, Hashable a) => Graph (Weighted d) a > VertexSelector a > VertexSelector a > Map (a, a) (Maybe Int)Source
2.2. igraph_shortest_paths_dijkstra
— Weighted shortest paths from some
sources.
This function is Dijkstra's algorithm to find the weighted shortest paths to all vertices from a single source. (It is run independently for the given sources.) It uses a binary heap for efficient implementation.
shortestPathsBellmanFord :: (Ord a, Hashable a) => Graph (Weighted d) a > VertexSelector a > VertexSelector a > Map (a, a) (Maybe Int)Source
2.3. igraph_shortest_paths_bellman_ford
— Weighted shortest paths from some
sources allowing negative weights.
This function is the BellmanFord algorithm to find the weighted shortest paths to all vertices from a single source. (It is run independently for the given sources.). If there are no negative weights, you are better off with igraph_shortest_paths_dijkstra() .
shortestPathsJohnson :: (Ord a, Hashable a) => Graph (Weighted d) a > VertexSelector a > VertexSelector a > Map (a, a) (Maybe Int)Source
2.4. igraph_shortest_paths_johnson
— Calculate shortest paths from some
sources using Johnson's algorithm.
See Wikipedia at http:en.wikipedia.orgwikiJohnson's_algorithm for Johnson's algorithm. This algorithm works even if the graph contains negative edge weights, and it is worth using it if we calculate the shortest paths from many sources.
If no edge weights are supplied, then the unweighted version, igraph_shortest_paths() is called.
If all the supplied edge weights are nonnegative, then Dijkstra's algorithm is used by calling igraph_shortest_paths_dijkstra().
:: Graph d a  
> a  from 
> VertexSelector a  to 
> [([a], [Edge d a])]  list of 
2.5. igraph_get_shortest_paths
— Calculates the shortest paths from/to one
vertex.
If there is more than one geodesic between two vertices, this function gives only one of them.
getShortestPathsDijkstraSource
:: Graph (Weighted d) a  
> a  from 
> VertexSelector a  to 
> [([a], [Edge (Weighted d) a])]  list of 
2.7. igraph_get_shortest_paths_dijkstra
— Calculates the weighted
shortest paths from/to one vertex.
If there is more than one path with the smallest weight between two vertices, this function gives only one of them.
getShortestPath :: Graph d a > a > a > ([a], [Edge d a])Source
2.6. igraph_get_shortest_path
— Shortest path from one vertex to another
one.
Calculates and returns a single unweighted shortest path from a given vertex to another one. If there are more than one shortest paths between the two vertices, then an arbitrary one is returned.
This function is a wrapper to igraph_get_shortest_paths(), for the special case when only one target vertex is considered.
getShortestPathDijkstra :: Graph (Weighted d) a > a > a > ([a], [Edge (Weighted d) a])Source
2.8. igraph_get_shortest_path_dijkstra
— Weighted shortest path from one
vertex to another one.
Calculates a single (positively) weighted shortest path from a single vertex to another one, using Dijkstra's algorithm.
This function is a special case (and a wrapper) to igraph_get_shortest_paths_dijkstra().
:: Graph d a  
> a  from 
> VertexSelector a  to 
> [[a]]  list of vertices along the shortest path from

2.9. igraph_get_all_shortest_paths
— Finds all shortest paths (geodesics)
from a vertex to all other vertices.
getAllShortestPathsDijkstraSource
:: Graph (Weighted d) a  
> a  from 
> VertexSelector a  to 
> [[a]]  list of vertices along the shortest path from

2.10. igraph_get_all_shortest_paths_dijkstra
— Finds all shortest paths
(geodesics) from a vertex to all other vertices.
:: Graph d a  
> Bool  Boolean, whether to consider directed paths. Ignored for undirected graphs. 
> Bool  What to do if the graph is not connected. If TRUE the average of the geodesics within the components will be returned, otherwise the number of vertices is used for the length of nonexisting geodesics. (The rationale behind this is that this is always longer than the longest possible geodesic in a graph.) 
> Double 
2.11. igraph_average_path_length
— Calculates the average geodesic length
in a graph.
:: Graph d a  
> Bool  Whether to consider directed paths in a directed graph (if not zero). This argument is ignored for undirected graphs. 
> ([Double], Double) 
2.12. igraph_path_length_hist
— Create a histogram of all shortest path lengths.
This function calculates a histogram, by calculating the shortest path length between each pair of vertices. For directed graphs both directions might be considered and then every pair of vertices appears twice in the histogram.
:: Graph d a  
> Bool  
> Bool  
> (Int, (a, a), [a])  the diameter of the graph, the starting/end vertices and the longest path 
2.13. igraph_diameter
— Calculates the diameter of a graph (longest
geodesic).
2.14. igraph_diameter_dijkstra
— Weighted diameter using Dijkstra's
algorithm, nonnegative weights only.
The diameter of a graph is its longest geodesic. I.e. the (weighted) shortest path is calculated for all pairs of vertices and the longest one is the diameter.
2.15. igraph_girth
— The girth of a graph is the length of the shortest
circle in it.
The current implementation works for undirected graphs only, directed graphs are treated as undirected graphs. Loop edges and multiple edges are ignored.
If the graph is a forest (ie. acyclic), then zero is returned.
This implementation is based on Alon Itai and Michael Rodeh: Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory of computing , 110, 1977. The first implementation of this function was done by Keith Briggs, thanks Keith.
eccentricity :: Graph d a > VertexSelector a > [(a, Int)]Source
2.16. igraph_eccentricity
— Eccentricity of some vertices
The eccentricity of a vertex is calculated by measuring the shortest distance from (or to) the vertex, to (or from) all vertices in the graph, and taking the maximum.
This implementation ignores vertex pairs that are in different components. Isolated vertices have eccentricity zero.
radius :: Graph d a > IntSource
2.17. igraph_radius
— Radius of a graph
The radius of a graph is the defined as the minimum eccentricity of its vertices, see igraph_eccentricity().
13.4 Graph Components
Note that there currently is an issue with GHCi and shared libraries on
x86_64 linux systems which will cause an error in those functions that
return graphs (e.g. inducedSubgraph
). See GHC Ticket #781
(http://hackage.haskell.org/trac/ghc/ticket/781). Statically compiling
your program or installing this module (and all it's dependencies) with
fPIC
should fix this issue.
subcomponent :: Graph d a > a > [a]Source
4.1. igraph_subcomponent
— The vertices in the same component as a given vertex.
inducedSubgraph :: Graph d a > VertexSelector a > SubgraphImplementation > Graph d aSource
4.2. igraph_induced_subgraph
— Creates a subgraph induced by the specified vertices.
This function collects the specified vertices and all edges between them to a new graph. As the vertex ids in a graph always start with zero, this function very likely needs to reassign ids to the vertices.
subgraphEdges :: Graph d a > EdgeSelector d a > Graph d aSource
4.3. igraph_subgraph_edges
— Creates a subgraph with the specified edges and their endpoints.
This function collects the specified edges and their endpoints to a new graph. As the vertex ids in a graph always start with zero, this function very likely needs to reassign ids to the vertices.
:: Graph d a  
> Connectedness  
> (Int, [Int])  (number of clusters, list of size of all clusters) 
4.5. igraph_clusters
— Calculates the (weakly or strongly) connected
components in a graph.
isConnected :: Graph d a > Connectedness > BoolSource
4.6. igraph_is_connected
— Decides whether the graph is (weakly or strongly) connected.
A graph with zero vertices (i.e. the null graph) is connected by definition.
decompose :: Graph d a > Connectedness > Int > Int > [Graph d a]Source
4.7. igraph_decompose
— Decompose a graph into connected components.
Create separate graph for each component of a graph. Note that the vertex ids in the new graphs will be different than in the original graph. (Except if there is only one component in the original graph.)
:: Graph d a  
> (Int, [[Edge d a]], [[Edge d a]], [[a]], [a])  (number of biconnected components, edges of spanning trees, edges of biconnected components, vertices of biconnected components, articulation points of the graph) 
4.9. igraph_biconnected_components
— Calculate biconnected components
A graph is biconnected if the removal of any single vertex (and its incident edges) does not disconnect it.
A biconnected component of a graph is a maximal biconnected subgraph of it. The biconnected components of a graph can be given by the partition of its edges: every edge is a member of exactly one biconnected component. Note that this is not true for vertices: the same vertex can be part of many biconnected components.
articulationPoints :: Graph d a > [a]Source
4.10. igraph_articulation_points
— Find the articulation points in a
graph.
A vertex is an articulation point if its removal increases the number of connected components in the graph.
13.5 Centrality Measures
closeness :: Ord a => Graph d a > VertexSelector a > Map a DoubleSource
5.1. igraph_closeness
— Closeness centrality calculations for some
vertices.
The closeness centrality of a vertex measures how easily other vertices can be reached from it (or the other way: how easily it can be reached from the other vertices). It is defined as the number of the number of vertices minus one divided by the sum of the lengths of all geodesics from/to the given vertex.
If the graph is not connected, and there is no path between two vertices, the number of vertices is used instead the length of the geodesic. This is always longer than the longest possible geodesic.
betweenness :: Ord a => Graph d a > VertexSelector a > Map a DoubleSource
5.2. igraph_betweenness
— Betweenness centrality of some vertices.
The betweenness centrality of a vertex is the number of geodesics going through it. If there are more than one geodesic between two vertices, the value of these geodesics are weighted by one over the number of geodesics.
edgeBetweenness :: Ord (Edge d a) => Graph d a > Map (Edge d a) DoubleSource
5.3. igraph_edge_betweenness
— Betweenness centrality of the edges.
The betweenness centrality of an edge is the number of geodesics going through it. If there are more than one geodesics between two vertices, the value of these geodesics are weighted by one over the number of geodesics.
:: Graph d a  
> VertexSelector a  
> Double  The damping factor (d in the original paper) 
> (Double, [(a, Double)]) 
5.4. igraph_pagerank
— Calculates the Google PageRank for the specified vertices.
:: Graph d a  
> VertexSelector a  
> Double  The damping factor (d in the original paper) 
> (Double, [(a, Double)]) 
5.6. igraph_personalized_pagerank
— Calculates the personalized Google PageRank for the specified vertices.
:: Graph d a  
> VertexSelector a  
> Double  The damping factor (d in the original paper) 
> VertexSelector a  IDs of the vertices used when resetting the random walk. 
> (Double, [(a, Double)]) 
5.7. igraph_personalized_pagerank_vs
— Calculates the personalized
Google PageRank for the specified vertices.
constraint :: Ord a => Graph d a > VertexSelector a > Map a DoubleSource
5.8. igraph_constraint
— Burt's constraint scores.
This function calculates Burt's constraint scores for the given vertices, also known as structural holes.
Burt's constraint is higher if ego has less, or mutually stronger related (i.e. more redundant) contacts. Burt's measure of constraint, C[i], of vertex i's ego network V[i], is defined for directed and valued graphs,
C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in V[], j != i)
for a graph of order (ie. number of vertices) N, where proportional tie strengths are defined as
p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i),
a[i,j] are elements of A and the latter being the graph adjacency matrix. For isolated vertices, constraint is undefined.
Burt, R.S. (2004). Structural holes and good ideas. American Journal of Sociology 110, 349399.
The first R version of this function was contributed by Jeroen Bruggeman.
:: Graph d a  
> VertexSelector a  
> Bool  count selfloops? 
> Int 
5.9. igraph_maxdegree
— Calculate the maximum degree in a graph (or set
of vertices).
The largest in, out or total degree of the specified vertices is calculated.
5.10. igraph_strength
— Strength of the vertices, weighted vertex degree
in other words.
In a weighted network the strength of a vertex is the sum of the weights of all incident edges. In a nonweighted network this is exactly the vertex degree.
:: Graph d a  
> Bool  If True the result will be scaled such that the absolute value of the maximum centrality is one. 
> (Double, [(a, Double)]) 
5.11. igraph_eigenvector_centrality
— Eigenvector centrality of the vertices
:: Graph d a  
> Bool  If True then the result will be scaled such that the absolute value of the maximum centrality is one. 
> (Double, [(a, Double)]) 
5.12. igraph_hub_score
— Kleinberg's hub scores
:: Graph d a  
> Bool  If True then the result will be scaled such that the absolute value of the maximum centrality is one. 
> (Double, [(a, Double)]) 
5.13. igraph_authority_score
— Kleinerg's authority scores
13.6 Estimating Centrality Measures
6.1. igraph_closeness_estimate
— Closeness centrality estimations for
some vertices.
The closeness centrality of a vertex measures how easily other vertices can be reached from it (or the other way: how easily it can be reached from the other vertices). It is defined as the number of the number of vertices minus one divided by the sum of the lengths of all geodesics from/to the given vertex. When estimating closeness centrality, igraph considers paths having a length less than or equal to a prescribed cutoff value.
If the graph is not connected, and there is no such path between two vertices, the number of vertices is used instead the length of the geodesic. This is always longer than the longest possible geodesic.
Since the estimation considers vertex pairs with a distance greater than the given value as disconnected, the resulting estimation will always be lower than the actual closeness centrality.
6.2. igraph_betweenness_estimate
— Estimated betweenness centrality of
some vertices.
The betweenness centrality of a vertex is the number of geodesics going through it. If there are more than one geodesic between two vertices, the value of these geodesics are weighted by one over the number of geodesics. When estimating betweenness centrality, igraph takes into consideration only those paths that are shorter than or equal to a prescribed length. Note that the estimated centrality will always be less than the real one.
6.3. igraph_edge_betweenness_estimate
— Estimated betweenness centrality
of the edges.
The betweenness centrality of an edge is the number of geodesics going through it. If there are more than one geodesics between two vertices, the value of these geodesics are weighted by one over the number of geodesics. When estimating betweenness centrality, igraph takes into consideration only those paths that are shorter than or equal to a prescribed length. Note that
13.7 Centralization
:: Ord a  
=> Graph d a  
> Bool  consider loop edges? 
> Bool  normalize centralization score? 
> (Map a Double, Double, Double)  (nodelevel degree scores, centralization scores, theoretical max) 
7.2. igraph_centralization_degree
— Calculate vertex degree and graph
centralization
This function calculates the degree of the vertices by passing its arguments to igraph_degree(); and it calculates the graph level centralization index based on the results by calling igraph_centralization().
centralizationBetweennessSource
:: Ord a  
=> Graph d a  
> Bool  normalize centralization score? 
> (Map a Double, Double, Double)  (nodelevel degree scores, centralization scores, theoretical max) 
7.3. igraph_centralization_betweenness
— Calculate vertex betweenness and
graph centralization
This function calculates the betweenness centrality of the vertices by passing its arguments to igraph_betweenness(); and it calculates the graph level centralization index based on the results by calling igraph_centralization().
:: Ord a  
=> Graph d a  
> Bool  normalize centralization score? 
> (Map a Double, Double, Double)  (nodelevel degree scores, centralization scores, theoretical max) 
7.4. igraph_centralization_closeness
— Calculate vertex closeness and
graph centralization
This function calculates the closeness centrality of the vertices by passing its arguments to igraph_closeness(); and it calculates the graph level centralization index based on the results by calling igraph_centralization().
centralizationEigenvectorCentralitySource
:: Graph d a  
> Bool  If True then the result will be scaled, such that the absolute value of the maximum centrality is one. 
> Bool  Boolean, whether to calculate a normalized centralization score. See igraph_centralization() for how the normalization is done. 
> (Double, Double, Double)  (leading eigenvalue, centralization score, theoretical max) 
7.5. igraph_centralization_eigenvector_centrality
— Calculate
eigenvector centrality scores and graph centralization
This function calculates the eigenvector centrality of the vertices by passing its arguments to igraph_eigenvector_centrality); and it calculates the graph level centralization index based on the results by calling igraph_centralization().
centralizationDegreeTMaxSource
7.6. igraph_centralization_degree_tmax
— Theoretical maximum for graph
centralization based on degree
This function returns the theoretical maximum graph centrality based on vertex degree.
There are two ways to call this function, the first is to supply a graph as the graph argument, and then the number of vertices is taken from this object, and its directedness is considered as well. The nodes argument is ignored in this case. The mode argument is also ignored if the supplied graph is undirected.
The other way is to supply a null pointer as the graph argument. In this case the nodes and mode arguments are considered.
The most centralized structure is the star. More specifically, for undirected graphs it is the star, for directed graphs it is the instar or the outstar.
centralizationBetweennessTMax :: Either (Graph d a) Int > DoubleSource
7.7. igraph_centralization_betweenness_tmax
— Theoretical maximum for
graph centralization based on betweenness
This function returns the theoretical maximum graph centrality based on vertex betweenness.
There are two ways to call this function, the first is to supply a graph as the graph argument, and then the number of vertices is taken from this object, and its directedness is considered as well. The nodes argument is ignored in this case. The directed argument is also ignored if the supplied graph is undirected.
The other way is to supply a null pointer as the graph argument. In this case the nodes and directed arguments are considered.
The most centralized structure is the star.
centralizationClosenessTMax :: Either (Graph d a) Int > DoubleSource
7.8. igraph_centralization_closeness_tmax
— Theoretical maximum for graph
centralization based on closeness
This function returns the theoretical maximum graph centrality based on vertex closeness.
There are two ways to call this function, the first is to supply a graph as the graph argument, and then the number of vertices is taken from this object, and its directedness is considered as well. The nodes argument is ignored in this case. The mode argument is also ignored if the supplied graph is undirected.
The other way is to supply a null pointer as the graph argument. In this case the nodes and mode arguments are considered.
The most centralized structure is the star.
centralizationEigenvectorCentralityTMaxSource
:: Either (Graph d a) Int  
> Bool  Whether to consider edge directions. This argument is ignored if graph is not a null pointer and it is undirected 
> Bool  Whether to rescale the nodelevel centrality scores to have a maximum of one 
> Double 
7.9. igraph_centralization_eigenvector_centrality_tmax
— Theoretical
maximum centralization for eigenvector centrality
This function returns the theoretical maximum graph centrality based on vertex eigenvector centrality.
There are two ways to call this function, the first is to supply a graph as the graph argument, and then the number of vertices is taken from this object, and its directedness is considered as well. The nodes argument is ignored in this case. The directed argument is also ignored if the supplied graph is undirected.
The other way is to supply a null pointer as the graph argument. In this case the nodes and directed arguments are considered.
The most centralized directed structure is the instar. The most centralized undirected structure is the graph with a single edge.
13.8 Similarity Measures
bibCoupling :: Graph d a > VertexSelector a > [(a, [(a, Int)])]Source
8.1. igraph_bibcoupling
— Bibliographic coupling.
The bibliographic coupling of two vertices is the number of other vertices they both cite, `igraph_bibcoupling()` calculates this. The bibliographic coupling score for each given vertex and all other vertices in the graph will be calculated.
cocitation :: Graph d a > VertexSelector a > [(a, [(a, Int)])]Source
8.2. igraph_cocitation
— Cocitation coupling.
Two vertices are cocited if there is another vertex citing both of them. `igraph_cocitation()` simply counts how many times two vertices are cocited. The cocitation score for each given vertex and all other vertices in the graph will be calculated.
:: Graph d a  
> VertexSelector a  
> Bool  Whether to include the vertices themselves in the neighbor sets 
> [(a, [(a, Double)])] 
8.3. igraph_similarity_jaccard
— Jaccard similarity coefficient for the
given vertices.
The Jaccard similarity coefficient of two vertices is the number of common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for some (or all) of the vertices.
:: Graph d a  
> [Edge d a]  
> Bool  Whether to include the vertices themselves in the neighbor sets 
> [(Edge d a, Double)] 
8.4. igraph_similarity_jaccard_pairs
— Jaccard similarity coefficient for
given vertex pairs.
The Jaccard similarity coefficient of two vertices is the number of common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for a list of vertex pairs.
:: Graph d a  
> EdgeSelector d a  
> Bool  Whether to include the vertices themselves in the neighbor sets 
> [(Edge d a, Double)] 
8.5. igraph_similarity_jaccard_es
— Jaccard similarity coefficient for a
given edge selector.
The Jaccard similarity coefficient of two vertices is the number of common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for the endpoints of edges in a given edge selector.
:: Graph d a  
> VertexSelector a  
> Bool  Whether to include the vertices themselves as their own neighbors 
> [(a, [(a, Double)])] 
8.6. igraph_similarity_dice
— Dice similarity coefficient.
The Dice similarity coefficient of two vertices is twice the number of common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for some (or all) of the vertices.
:: Graph d a  
> [Edge d a]  
> Bool  Whether to include the vertices themselves as their own neighbors 
> [(Edge d a, Double)] 
8.7. igraph_similarity_dice_pairs
— Dice similarity coefficient for given
vertex pairs.
The Dice similarity coefficient of two vertices is twice the number of common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for a list of vertex pairs.
:: Graph d a  
> EdgeSelector d a  
> Bool  Whether to include the vertices themselves as their own neighbors 
> [(Edge d a, Double)] 
8.8. igraph_similarity_dice_es
— Dice similarity coefficient for a given
edge selector.
The Dice similarity coefficient of two vertices is twice the number of common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for the endpoints of edges in a given edge selector.
similarityInverseLogWeighted :: Graph d a > VertexSelector a > [(a, [(a, Double)])]Source
8.9. igraph_similarity_inverse_log_weighted
— Vertex similarity based on
the inverse logarithm of vertex degrees.
The inverse logweighted similarity of two vertices is the number of their common neighbors, weighted by the inverse logarithm of their degrees. It is based on the assumption that two vertices should be considered more similar if they share a lowdegree common neighbor, since highdegree common neighbors are more likely to appear even by pure chance.
Isolated vertices will have zero similarity to any other vertex. Selfsimilarities are not calculated.
See the following paper for more details: Lada A. Adamic and Eytan Adar: Friends and neighbors on the Web. Social Networks, 25(3):211230, 2003.
13.9 Spanning Tress
minimumSpanningTree :: Graph d a > [Edge d a]Source
9.1. igraph_minimum_spanning_tree
— Calculates one minimum spanning tree of a graph.
If the graph has more minimum spanning trees (this is always the case, except if it is a forest) this implementation returns only the same one.
Directed graphs are considered as undirected for this computation.
If the graph is not connected then its minimum spanning forest is returned. This is the set of the minimum spanning trees of each component.
minimumSpanningTreeUnweighted :: IsUnweighted d => Graph d a > Graph d aSource
9.2. igraph_minimum_spanning_tree_unweighted
— Calculates one minimum
spanning tree of an unweighted graph.
minimumSpanningTreePrim :: IsUnweighted d => Graph (Weighted d) a > Graph (Weighted d) aSource
9.3. igraph_minimum_spanning_tree_prim
— Calculates one minimum
spanning tree of a weighted graph.
13.10 Transitivity or Clustering Coefficient
transitivityUndirected :: Graph d a > DoubleSource
10.1. igraph_transitivity_undirected
— Calculates the transitivity
(clustering coefficient) of a graph.
The transitivity measures the probability that two neighbors of a vertex are connected. More precisely, this is the ratio of the triangles and connected triples in the graph, the result is a single real number. Directed graphs are considered as undirected ones.
Note that this measure is different from the local transitivity measure (see `igraph_transitivity_local_undirected()` ) as it calculates a single value for the whole graph. See the following reference for more details:
S. Wasserman and K. Faust: Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
Clustering coefficient is an alternative name for transitivity.
transitivityLocalUndirected :: Graph d a > VertexSelector a > [(a, Double)]Source
10.2. igraph_transitivity_local_undirected
— Calculates the local
transitivity (clustering coefficient) of a graph.
The transitivity measures the probability that two neighbors of a vertex are connected. In case of the local transitivity, this probability is calculated separately for each vertex.
Note that this measure is different from the global transitivity measure (see igraph_transitivity_undirected() ) as it calculates a transitivity value for each vertex individually. See the following reference for more details:
D. J. Watts and S. Strogatz: Collective dynamics of smallworld networks. Nature 393(6684):440442 (1998).
Clustering coefficient is an alternative name for transitivity.
transitivityAvglocalUndirected :: Graph d a > DoubleSource
10.3. igraph_transitivity_avglocal_undirected
— Average local transitivity
(clustering coefficient).
The transitivity measures the probability that two neighbors of a vertex are connected. In case of the average local transitivity, this probability is calculated for each vertex and then the average is taken. Vertices with less than two neighbors require special treatment, they will either be left out from the calculation or they will be considered as having zero transitivity, depending on the mode argument.
Note that this measure is different from the global transitivity measure (see `igraph_transitivity_undirected()` ) as it simply takes the average local transitivity across the whole network. See the following reference for more details:
D. J. Watts and S. Strogatz: Collective dynamics of smallworld networks. Nature 393(6684):440442 (1998).
Clustering coefficient is an alternative name for transitivity.
transitivityBarrat :: Graph d a > VertexSelector a > [(a, Double)]Source
10.4. igraph_transitivity_barrat
— Weighted transitivity, as defined by A.
Barrat.
This is a local transitivity, i.e. a vertexlevel index. For a given vertex i, from all triangles in which it participates we consider the weight of the edges incident on i. The transitivity is the sum of these weights divided by twice the strength of the vertex (see `igraph_strength()`) and the degree of the vertex minus one. See Alain Barrat, Marc Barthelemy, Romualdo PastorSatorras, Alessandro Vespignani: The architecture of complex weighted networks, Proc. Natl. Acad. Sci. USA 101, 3747 (2004) at http:arxiv.orgabscondmat/0311416 for the exact formula.
13.12 Spectral properties
12.1. igraph_laplacian
— Returns the Laplacian matrix of a graph
The graph Laplacian matrix is similar to an adjacency matrix but contains 1's instead of 1's and the vertex degrees are included in the diagonal. So the result for edge ij is 1 if i!=j and is equal to the degree of vertex i if i==j. igraph_laplacian will work on a directed graph; in this case, the diagonal will contain the outdegrees. Loop edges will be ignored.
The normalized version of the Laplacian matrix has 1 in the diagonal and 1/sqrt(d[i]d[j]) if there is an edge from i to j.
The first version of this function was written by Vincent Matossian.
13.14 Mixing patterns
:: Eq vertexType  
=> Graph d (vertexType, a)  
> Bool  whether to consider edge directions in a directed graph. It is ignored for undirected graphs 
> Double 
14.1. igraph_assortativity_nominal
— Assortativity of a graph based on
vertex categories
Assuming the vertices of the input graph belong to different categories, this function calculates the assortativity coefficient of the graph. The assortativity coefficient is between minus one and one and it is one if all connections stay within categories, it is minus one, if the network is perfectly disassortative. For a randomly connected network it is (asymptotically) zero.
See equation (2) in M. E. J. Newman: Mixing patterns in networks, Phys. Rev. E 67, 026126 (2003) (http:arxiv.orgabscondmat/0209450) for the proper definition.
:: (Eq vertexTypeIncoming, Eq vertexTypeOutgoing)  
=> Graph d (vertexTypeIncoming, vertexTypeOutgoing, a)  
> Bool  whether to consider edge directions for directed graphs. It is ignored for undirected graphs 
> Double 
14.2. igraph_assortativity
— Assortativity based on numeric properties of
vertices
This function calculates the assortativity coefficient of the input graph. This coefficient is basically the correlation between the actual connectivity patterns of the vertices and the pattern expected from the distribution of the vertex types.
See equation (21) in M. E. J. Newman: Mixing patterns in networks, Phys. Rev. E 67, 026126 (2003) (http:arxiv.orgabscondmat/0209450) for the proper definition. The actual calculation is performed using equation (26) in the same paper for directed graphs, and equation (4) in M. E. J. Newman: Assortative mixing in networks, Phys. Rev. Lett. 89, 208701 (2002) (http:arxiv.orgabscondmat0205405) for undirected graphs.
:: Graph d a  
> Bool  whether to consider edge directions for directed graphs. This
argument is ignored for undirected graphs. Supply 
> Double 
14.3. igraph_assortativity_degree
— Assortativity of a graph based on vertex
degree
Assortativity based on vertex degree, please see the discussion at the documentation of igraph_assortativity() for details.
13.15 KCores
coreness :: Graph d a > [(Double, a)]Source
15.1. igraph_coreness
— Finding the coreness of the vertices in a network.
The kcore of a graph is a maximal subgraph in which each vertex has at least degree k. (Degree here means the degree in the subgraph of course.). The coreness of a vertex is the highest order of a kcore containing the vertex.
This function implements the algorithm presented in Vladimir Batagelj, Matjaz Zaversnik: An O(m) Algorithm for Cores Decomposition of Networks.
13.16 Topological sorting, directed acyclic graphs
isDAG :: Graph d a > BoolSource
16.1. igraph_is_dag
— Checks whether a graph is a directed acyclic graph
(DAG) or not.
A directed acyclic graph (DAG) is a directed graph with no cycles.
topologicalSorting :: Graph d a > [a]Source
16.2. igraph_topological_sorting
— Calculate a possible topological sorting
of the graph.
A topological sorting of a directed acyclic graph is a linear ordering of its nodes where each node comes before all nodes to which it has edges. Every DAG has at least one topological sort, and may have many. This function returns a possible topological sort among them. If the graph is not acyclic (it has at least one cycle), a partial topological sort is returned and a warning is issued.
feedbackArcSet :: Graph d a > FASAlgorithm > [a]Source
16.3. igraph_feedback_arc_set
— Calculates a feedback arc set of the graph
using different
A feedback arc set is a set of edges whose removal makes the graph acyclic. We are usually interested in minimum feedback arc sets, i.e. sets of edges whose total weight is minimal among all the feedback arc sets.
For undirected graphs, the problem is simple: one has to find a maximum weight spanning tree and then remove all the edges not in the spanning tree. For directed graphs, this is an NPhard problem, and various heuristics are usually used to find an approximate solution to the problem. This function implements a few of these heuristics.
13.17 Maximum cardinality search, graph decomposition, chordal graphs
maximumCardinalitySearch :: Graph d a > [(Int, a)]Source
17.1. igraph_maximum_cardinality_search
— Maximum cardinality search
This function implements the maximum cardinality search algorithm discussed in Robert E Tarjan and Mihalis Yannakakis: Simple lineartime algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal of Computation 13, 566579, 1984.
17.2. igraph_is_chordal
— Decides whether a graph is chordal
A graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes.