Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Structural Similarity: Spectral Methods for Relaxed Blockmodeling

Structural Similarity: Spectral Methods for Relaxed Blockmodeling In this paper we propose the concept of structural similarity as a relaxation of blockmodeling in social network analysis. Most previous approaches attempt to relax the constraints on partitions, for instance, that of being a structural or regular equivalence to being approximately structural or regular, respectively. In contrast, our approach is to relax the partitions themselves: structural similarities yield similarity values instead of equivalence or non-equivalence of actors, while strictly obeying the requirement made for exact regular equivalences. Structural similarities are based on a vector space interpretation and yield efficient spectral methods that, in a more restrictive manner, have been successfully applied to difficult combinatorial problems such as graph coloring. While traditional blockmodeling approaches have to rely on local search heuristics, our framework yields algorithms that are provably optimal for specific data-generation models. Furthermore, the stability of structural similarities can be well characterized making them suitable for the analysis of noisy or dynamically changing network data. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Classification Springer Journals

Structural Similarity: Spectral Methods for Relaxed Blockmodeling

Brandes, Ulrik; Lerner, Jürgen
Journal of Classification , Volume 27 (3) – Oct 16, 2010
Download PDF
28 pages

Loading next page...
 
/lp/springer-journals/structural-similarity-spectral-methods-for-relaxed-blockmodeling-0Cx7VTfsSU

References (48)

Publisher
Springer Journals
Copyright
Copyright © 2010 by Springer Science+Business Media, LLC
Subject
Statistics; Marketing ; Psychometrics; Signal, Image and Speech Processing; Bioinformatics; Pattern Recognition; Statistical Theory and Methods
ISSN
0176-4268
eISSN
1432-1343
DOI
10.1007/s00357-010-9062-8
Publisher site
See Article on Publisher Site

Abstract

In this paper we propose the concept of structural similarity as a relaxation of blockmodeling in social network analysis. Most previous approaches attempt to relax the constraints on partitions, for instance, that of being a structural or regular equivalence to being approximately structural or regular, respectively. In contrast, our approach is to relax the partitions themselves: structural similarities yield similarity values instead of equivalence or non-equivalence of actors, while strictly obeying the requirement made for exact regular equivalences. Structural similarities are based on a vector space interpretation and yield efficient spectral methods that, in a more restrictive manner, have been successfully applied to difficult combinatorial problems such as graph coloring. While traditional blockmodeling approaches have to rely on local search heuristics, our framework yields algorithms that are provably optimal for specific data-generation models. Furthermore, the stability of structural similarities can be well characterized making them suitable for the analysis of noisy or dynamically changing network data.

Journal

Journal of Classification – Springer Journals

Published: Oct 16, 2010

There are no references for this article.