Contents
- Index
NETWORK > SUBGROUPS > LAMBDA SETS
PURPOSE List all lambda sets of a graph.
DESCRIPTION The edge connectivity of a pair of vertices is the minimum number of edges which must be deleted so that there is no path connecting them.
A lambda set is a maximal subset of vertices with the property that the edge connectivity of any pair of vertices within the subset is strictly greater than the edge connectivity of any pair of vertices, one of which is in the subset and one of which is outside.
Hence if l(a,b) represents the edge-connectivity of two vertices a and b from a graph G(V,E) then a subset S is a lambda set if it is the maximal set with the property that for all a,b,c e S and d e V-S then l(a,b) > l(c,d).
The algorithm employed first computes the maximum flow (i.e. the connectivity) between all pairs of vertices (see NETWORKS>COHESION>MAX FLOW) and uses this information to construct the lambda sets.
PARAMETERS
Input dataset:
Name of file containing network to be analyzed. Data type: Graph.
(Output) Partition Matrix: (Default = 'LambdaSetsPart')
Name of file which contains partition indicator matrix which corresponds to the hierarchical clustering produced in the LOG FILE. A value of k in a column labeled i and row j means that actor j is in partition k; the other members of the partition form a lambda set with minimum edge-connectivity i. Actor k is always a member of partition k, and is a representative label for the group. This matrix is not displayed in the LOG FILE.
(Output) Lambda Matrix: (Default = 'LambdaSetsFlow')
Name of data file containing maximum flows between all pairs of vertices.
(Output) Permutation Vector: (Default = 'LambdaSetsPerm')
Name of data file which contains the permutation of the nodes used in constructing the single link hierarchical clustering diagram below.
LOG FILE An hierarchical clustering dendrogram, each level corresponding to a different degree of minimum internal edge-connectivity. This value characterizes the lambda set. The level at which any pair of actors are aggregated is the point at which both can be reached by tracing from the start to the actors from right to left. The scale at the top gives the level at which they are clustered. The diagram can be printed or saved. Parts of the diagram can be viewed by moving the mouse to the beginning of a line in the dendrogram and clicking. The first click will highlight a portion of the diagram and the second click will display just the highlighted portion. To return to the original right click on the mouse. There is also a simple zoom facility simply change the values and then press enter. If the labels need to be edited (particularly the scale labels) then you should take the partition indicator matrix into the spreadsheet editor remove or reduce the labels and then submit the edited data to Tools>Dendrogram>Draw. In the clustering diagram each level corresponding to a different value of 'k' in k-core. Behind the dendrogram is a clustering diagram representing the same thing. The columns are rearranged and labeled. A '·' in row labeled i column label j indicates that vertex j is not in a lambda set of minimum connectivity i. An 'X' indicates that vertex j is a member of the lambda set, all other members of j's lambda set are found by tracing along row labeled i in both directions from column j until a space is encountered in each direction. The column labels corresponding to an 'X' which are connected to j's X are all members of j's lambda set with minimum connectivity i.
The single link hierarchical diagram is followed by a maximum flow matrix. The maximum flow between i and j is given by the value in row i column j. The diagonal is set equal to the number of vertices, theoretically this value should be infinite.
TIMING 0(N^4).
COMMENTS Note this algorithm works on integer valued graphs by the natural extension of connectivity to minimum weight cutsets.
REFERENCES Borgatti S P, Everett M G and Shirey P R (1990). 'LS Sets, Lambda Sets and other cohesive subsets'. Social Networks 12, 337-357.