Description
Map a clustering result onto a graph, and compute the membership degree
between each node and each cluster, on the basis of egdes linking this
node to the cluster.
The result is a membership table, indicating the membership coefficient
of each node (row) to each cluster (column).
The result can be interpreted as a 'fuzzy clustering' of a graph, where
nodes can belong to multiple clusters, with various degree of
membership.
Authors
Options
Input and output formats
Graph format
The accepted input formats are GML, tab-delimited and adjacency matrix.
For more explanations about these, refer to the manual of convert-graph.
Classification format
A two-column file with column corresponding respectively to the node name and to the cluster name.
Output format
A tab-delimited text file with rows correponding to nodes and columns to clusters.
Number of Decimals
Number of decimals of the membership values.
Statistics
In assigning the membership of a node to a cluster, there are several
possiblities (option -stat):
weight
The membership of node n for cluster c is is the fraction of edge
weights linking node n to cluster i (W(n,c)):
Nc N
Mw(n,c)= SUM[W(n,i)] / SUM[W(n,j)]
i j
where W(n,i) is the weight of the edge between nodes n and i, i is the index for the nodes Nc belonging to
cluster c, and j is the index for all nodes N.
relw
The weight of the connections of a node to a given cluster are
normalized to the size of the cluster:
Nc K Nk
Mrw(n,c)= (SUM[W(n,i)]/Nc) / SUM (SUM[W(n,j)/Nk])
i k j
where K is the set of all clusters, the other symbols are defined as above.
The relative weight reduces the bias of membership coefficients
towards large clusters
edge
The membership Me(n,c) of node n for a cluster c is the number of
edges connecting node n to any node belonging to cluster c divided
by the total number of edges connecting node n:
Nc N
Me(n,c)= SUM[E(n,i)]/ SUM[E(n,j)]
i j
where E(n,i) is a boolean variable indicating if there is an edge
between nodes n and i, the other symbols are defined as above.
reledge
The number of edges of a node to a given cluster are normalized to
the size of the cluster:
Nc K Nk
Mre(n,c)= (SUM[E(n,i)]/Nc) / SUM (SUM[E(n,j)/Nk])
i k j
Column specifications (only for tab-delimited format)
Source and target column. Columns containing the source and target nodes. Also valid for undirected graphs
Weight column. Column containing the weight on the edge. If no weight is specified, the stat option is edge. If weight column is set, but weights are not real numbers, the stat will switch from weight to edge or from relative weight to relative edge, depending on the option selected.
Results
Membership Matrix
Rows correspond to nodes and columns correspond to clusters. The entry M [i,j] indicates the membership of node i to cluster j.