The complexity of social networks: theoretical and empirical findings

A great deal of work in recent years has been devoted to the topic of “complexity”, its measurement, and its implications. Here, the notion of algorithmic complexity is applied to the analysis of social networks. Structural features of theoretical importance — such as structural equivalence classes...

Full description

Saved in:
Bibliographic Details
Published in:Social networks 2001, Vol.23 (1), p.31-72
Main Author: Butts, Carter T.
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Data analysis
Entropy
Equivalence
Graph distribution
Graph Theory
Graphs
History, theory and methodology
Methodology
Methodology (Data Analysis)
Network Analysis
Networks
Simulation techniques
Social Networks
Sociology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A great deal of work in recent years has been devoted to the topic of “complexity”, its measurement, and its implications. Here, the notion of algorithmic complexity is applied to the analysis of social networks. Structural features of theoretical importance — such as structural equivalence classes — are shown to be strongly related to the algorithmic complexity of graphs, and these results are explored using analytical and simulation methods. Analysis of the complexity of a variety of empirically derived networks suggests that many social networks are nearly as complex as their source entropy, and thus that their structure is roughly in line with the conditional uniform graph distribution hypothesis. Implications of these findings for network theory and methodology are also discussed.
ISSN:0378-8733
1879-2111
DOI:10.1016/S0378-8733(01)00030-2