Premium
An algorithm for finding simultaneous homomorphic correspondences between graphs and their image graphs
Author(s) -
Heil Gregory H.,
White Harrison C.
Publication year - 1976
Publication title -
behavioral science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.371
H-Index - 45
eISSN - 1099-1743
pISSN - 0005-7940
DOI - 10.1002/bs.3830210105
Subject(s) - homomorphic encryption , image (mathematics) , computer science , algorithm , graph , construct (python library) , binary number , theoretical computer science , set (abstract data type) , block (permutation group theory) , matrix (chemical analysis) , mathematics , artificial intelligence , combinatorics , arithmetic , computer security , encryption , materials science , composite material , programming language
This paper concerns networks within human systems at the level of the group. We wish to abstract significant structural features from social networks. Each kind of observed tie in a population, reported as a square binary matrix, is compared with an image graph on a smaller set of nodes, called blocks. Correspondences between persons and blocks are found for which each image is the homomorphic image of that observed graph. An algorithm for this purpose is implemented in the APL language. The central construct is a four‐dimensional array reporting conflicts, from all graphs, between each possible assignment of one person to a block and each possible assignment of another person. Results are given for a model on three blocks applied to observed graphs of eight types of tie among 18 persons.