1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/community.R
\name{cluster_optimal}
\alias{cluster_optimal}
\alias{optimal.community}
\title{Optimal community structure}
\usage{
cluster_optimal(graph, weights = NULL)
}
\arguments{
\item{graph}{The input graph. Edge directions are ignored for directed
graphs.}
\item{weights}{Optional positive weight vector for optimizing weighted
modularity. If the graph has a \code{weight} edge attribute, then this is
used by default. Supply \code{NA} to ignore the weights of a weighted graph.}
}
\value{
\code{cluster_optimal} returns a \code{\link{communities}} object,
please see the \code{\link{communities}} manual page for details.
}
\description{
This function calculates the optimal community structure of a graph, by
maximizing the modularity measure over all possible partitions.
}
\details{
This function calculates the optimal community structure for a graph, in
terms of maximal modularity score.
The calculation is done by transforming the modularity maximization into an
integer programming problem, and then calling the GLPK library to solve
that. Please the reference below for details.
Note that modularity optimization is an NP-complete problem, and all known
algorithms for it have exponential time complexity. This means that you
probably don't want to run this function on larger graphs. Graphs with up to
fifty vertices should be fine, graphs with a couple of hundred vertices
might be possible.
}
\examples{
## Zachary's karate club
g <- make_graph("Zachary")
## We put everything into a big 'try' block, in case
## igraph was compiled without GLPK support
try({
## The calculation only takes a couple of seconds
oc <- cluster_optimal(g)
## Double check the result
print(modularity(oc))
print(modularity(g, membership(oc)))
## Compare to the greedy optimizer
fc <- cluster_fast_greedy(g)
print(modularity(fc))
}, silent=TRUE)
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\references{
Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke,
Martin Hoefer, Zoran Nikoloski, Dorothea Wagner: On Modularity Clustering,
\emph{IEEE Transactions on Knowledge and Data Engineering} 20(2):172-188,
2008.
}
\seealso{
\code{\link{communities}} for the documentation of the result,
\code{\link{modularity}}. See also \code{\link{cluster_fast_greedy}} for a
fast greedy optimizer.
}
\keyword{graphs}
|
