Search

In this paper, we explore the structure of the set of all regular equivalences (White and Reitz 1983), proving that it forms a lattice, and suggest a general approach to computing certain elements of the lattice. The resulting algorithm represents a useful complement to the White and Reitz algorithm, which can only find the maximal regular equivalence of a graph. Using this algorithm, it is possible to compute several well-known equivalences, such as structural equivalence. (Lorrain and White 1971), automorphic equivalence (Everett and Borgatti 1988), and Winship-Pattison equivalence (Winship and Mandel 1983). In addition, any number of other useful equivalences may be generated, providing suitable mathematical descriptions of them are available. [ABSTRACT FROM AUTHOR]

The orbits or a graph, digraph or network provide an effective definition for role equivalence since they are a natural generalization of the principle of substitutability of structural equivalence. Calculation of the orbits is a computationally difficult task but in this paper we present a fast and efficient algorithm which finds the orbits of a large class of graphs. In addition, we suggest a simple measure of role similarity based upon the constructions contained within the algorithm. This makes it possible to perform a role analysis when only a limited number of automorphisms exist. [ABSTRACT FROM AUTHOR]

A new concept of role similarity is presented; this definition is a generalisation of structural equivalence but is stricter than the idea of regular equivalence of White and Reitz (:1983). This new definition forms a standard part of graph theory literature and as such has been well researched. Consequently a complexity measure first proposed by Mowshowitz (1968a,b,c) can be given a definite meaning in terms of network concepts. A new measure of structural complexity based on role similarity is also introduced. [ABSTRACT FROM AUTHOR]

In this paper we show how the algorithm EBLOC can be extended to deal with valued data directly. The technique is then applied to Sampson's (1969) monastery data and comparisons are made with the original EBLOC algorithm. [ABSTRACT FROM AUTHOR]

Everett (1982) has proposed a graph theoretic blocking procedure for social networks. In this paper we give a comprehensive description of the implementation of this procedure with special reference to a FORTRAN program contained in the Appendix. [ABSTRACT FROM AUTHOR]

Everett and Nieminen have extended the Boyle homomorphism from undirected to directed graphs. Some sociological considerations implemented in conjunction with the homomorphism, indicate the structural importance of small cycles. These cycles are then used to construct an algorithm, which will produce a blocking of a social network. The algorithm is then tested on Sampson's monastery data (Sampson 1969). [ABSTRACT FROM AUTHOR]

A new method is described for optimizing graph parti tions that arise in mapping unstructured mesh calcula tions to parallel computers. The method employs a combination of iterative techniques to evenly balance the workload and minimize the number and volume of interprocessor communications. When combined with a fast direct-partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two- stage process proves itself to be a powerful and flexi ble solution to the static graph-partitioning problem. A clustering technique can also be employed to speed up the whole process. Experiments, on graphs with up to a million nodes, indicate that the resulting code is up to an order of magnitude faster than existing state- of-the-art techniques such as Multilevel Recursive Spectral Bisection, while providing partitions of equiv alent quality. [ABSTRACT FROM PUBLISHER]