-
-
Notifications
You must be signed in to change notification settings - Fork 203
/
Copy pathmodularity.igraph.Rd
130 lines (116 loc) · 4.89 KB
/
modularity.igraph.Rd
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/community.R
\name{modularity.igraph}
\alias{modularity.igraph}
\alias{modularity}
\alias{modularity_matrix}
\title{Modularity of a community structure of a graph}
\usage{
\method{modularity}{igraph}(x, membership, weights = NULL, resolution = 1, directed = TRUE, ...)
modularity_matrix(
graph,
membership,
weights = NULL,
resolution = 1,
directed = TRUE
)
}
\arguments{
\item{x, graph}{The input graph.}
\item{membership}{Numeric vector, one value for each vertex, the membership
vector of the community structure.}
\item{weights}{If not \code{NULL} then a numeric vector giving edge weights.}
\item{resolution}{The resolution parameter. Must be greater than or equal to
0. Set it to 1 to use the classical definition of modularity.}
\item{directed}{Whether to use the directed or undirected version of
modularity. Ignored for undirected graphs.}
\item{\dots}{Additional arguments, none currently.}
}
\value{
For \code{modularity()} a numeric scalar, the modularity score of the
given configuration.
For \code{modularity_matrix()} a numeric square matrix, its order is the number of
vertices in the graph.
}
\description{
This function calculates how modular is a given division of a graph into
subgraphs.
}
\details{
\code{modularity()} calculates the modularity of a graph with respect to the
given \code{membership} vector.
The modularity of a graph with respect to some division (or vertex types)
measures how good the division is, or how separated are the different vertex
types from each other. It defined as \deqn{Q=\frac{1}{2m} \sum_{i,j}
(A_{ij}-\gamma\frac{k_i k_j}{2m})\delta(c_i,c_j),}{Q=1/(2m) * sum( (Aij-gamma*ki*kj/(2m)
) delta(ci,cj),i,j),} here \eqn{m} is the number of edges, \eqn{A_{ij}}{Aij}
is the element of the \eqn{A} adjacency matrix in row \eqn{i} and column
\eqn{j}, \eqn{k_i}{ki} is the degree of \eqn{i}, \eqn{k_j}{kj} is the degree
of \eqn{j}, \eqn{c_i}{ci} is the type (or component) of \eqn{i},
\eqn{c_j}{cj} that of \eqn{j}, the sum goes over all \eqn{i} and \eqn{j}
pairs of vertices, and \eqn{\delta(x,y)}{delta(x,y)} is 1 if \eqn{x=y} and 0
otherwise. For directed graphs, it is defined as
\deqn{Q = \frac{1}{m} \sum_{i,j} (A_{ij}-\gamma
\frac{k_i^{out} k_j^{in}}{m})\delta(c_i,c_j).}{Q=1/(m) * sum(
(Aij-gamma*ki^out*kj^in/(m) ) delta(ci,cj),i,j).}
The resolution parameter \eqn{\gamma}{gamma} allows weighting the random
null model, which might be useful when finding partitions with a high
modularity. Maximizing modularity with higher values of the resolution
parameter typically results in more, smaller clusters when finding
partitions with a high modularity. Lower values typically results in fewer,
larger clusters. The original definition of modularity is retrieved when
setting \eqn{\gamma}{gamma} to 1.
If edge weights are given, then these are considered as the element of the
\eqn{A} adjacency matrix, and \eqn{k_i}{ki} is the sum of weights of
adjacent edges for vertex \eqn{i}.
\code{modularity_matrix()} calculates the modularity matrix. This is a dense matrix,
and it is defined as the difference of the adjacency matrix and the
configuration model null model matrix. In other words element
\eqn{M_{ij}}{M[i,j]} is given as \eqn{A_{ij}-d_i
d_j/(2m)}{A[i,j]-d[i]d[j]/(2m)}, where \eqn{A_{ij}}{A[i,j]} is the (possibly
weighted) adjacency matrix, \eqn{d_i}{d[i]} is the degree of vertex \eqn{i},
and \eqn{m} is the number of edges (or the total weights in the graph, if it
is weighed).
}
\examples{
g <- make_full_graph(5) \%du\% make_full_graph(5) \%du\% make_full_graph(5)
g <- add_edges(g, c(1, 6, 1, 11, 6, 11))
wtc <- cluster_walktrap(g)
modularity(wtc)
modularity(g, membership(wtc))
}
\references{
Clauset, A.; Newman, M. E. J. & Moore, C. Finding community
structure in very large networks, \emph{Physical Review E} 2004, 70, 066111
}
\seealso{
\code{\link[=cluster_walktrap]{cluster_walktrap()}},
\code{\link[=cluster_edge_betweenness]{cluster_edge_betweenness()}},
\code{\link[=cluster_fast_greedy]{cluster_fast_greedy()}}, \code{\link[=cluster_spinglass]{cluster_spinglass()}},
\code{\link[=cluster_louvain]{cluster_louvain()}} and \code{\link[=cluster_leiden]{cluster_leiden()}} for
various community detection methods.
Community detection
\code{\link{as_membership}()},
\code{\link{cluster_edge_betweenness}()},
\code{\link{cluster_fast_greedy}()},
\code{\link{cluster_fluid_communities}()},
\code{\link{cluster_infomap}()},
\code{\link{cluster_label_prop}()},
\code{\link{cluster_leading_eigen}()},
\code{\link{cluster_leiden}()},
\code{\link{cluster_louvain}()},
\code{\link{cluster_optimal}()},
\code{\link{cluster_spinglass}()},
\code{\link{cluster_walktrap}()},
\code{\link{compare}()},
\code{\link{groups}()},
\code{\link{make_clusters}()},
\code{\link{membership}()},
\code{\link{plot_dendrogram}()},
\code{\link{split_join_distance}()}
}
\author{
Gabor Csardi \email{[email protected]}
}
\concept{community}
\keyword{graphs}