Dynamic Social Network Modeling and Analysis Workshop Summary and Papers (2003) / Chapter Skim
Currently Skimming:
Spectral Methods for Analyzing and Visualizing Networks: An Introduction
Spectral Methods for Analyzing and Visualizing Networks: An Introduction
Pages 209-228
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 209... ...
Richards School of Communication Simon Fraser University Bu~naby BC Canada V5A- 1 S6 seary~sfi~.ca richards~sfi~.ca Abstract Network analysis begins with data that describes the set of relationships among the members of a system. The goal of analysis is to obtain Domthe low-level relational data a higher-level description of the structure of the system which identifies venous kinds of patterns In the set of relationships.
|
From page 210... ...
We win also introduce two other matrices related to A: · the Laplacian: L=D-A · the Normal: N=D-'A and wiD discuss the properties ofthe spectrum arid associated eigenvectors of A, A, and N ~ We have introduced some notation which will be followed throughout: · mamces are represented by bold capitals: D (column-)
|
From page 211... ...
Na; ajT for any power N and this allows an easy way of calculating powers of A, assuming we have already calculated all the eigenpairs (a, a i ~ Another important property ofthe spectral decomposition is the approximation property.
|
From page 214... ...
For N the coefficients of the characteristic equation are harder to interpret except In special cases, but the eigenvalues encode information about both the cycle and tree structure of G D - ASPIC SOCIAL N~TWORKMODE:L~G AND ANALYSIS
|
From page 215... ...
= number of spanning trees of G In the last example we see how details ofthe degree distribution are also encoded in the spectrum. Fan Chung uses this to derive two remarkable bounds (see Chung, 1995 for details)
|
From page 217... ...
With (5) we can teD how many eigenvectors we need to explain most ofthe x2 ofthe network.7 Compositions The Kronecker product of two binary matrices Al and A2 makes a copy of Al for each 1 in A2.
|
From page 218... ...
. Other researchers have used 12, 13 8 Hagen also uses deviations from median 218 DYNAMIC SOCIAL N~TWO~MOD~G ^D ANALYSIS
|
From page 219... ...
for a formal derivation and proof DYNAMIC SOCIAL N~TWORKAlODE~G kD TRYSTS 219
|
From page 221... ...
(1995~. Spectral Graph Theory, CBMS Lecture Notes, AMS Publication.
|
From page 222... ...
(1981~. The NEGOPY Network Analysis Program, Social Networks, 3~3~: 21~224.
|
From page 223... ...
Left: as the Cartesian sum of three paths producing a threedimensional grid. Right: as the Kronecker product producing a bipartite graph DYNAMIC SOCIAL N~TWO~MODEL~G ED ^^YSIS 223
|
From page 226... ...
In graph theory, the resulting set of eigenvalues is referred to as the graph spectrum, in analogy to the continuous spectrum from continuous spectral analysis methods such as Fourier analysis. In Fourier analysis, the spectrum is understood to refer to the weighting of sines and cosines, whereas the discrete graph spectrum (eigenvalues)
|
From page 227... ...
In social networks, links are often called ties. link list: A sparse format for stonng ~nfonnation in a network.
|
From page 228... ...
In social networks, nodes are often called actors. normal spectrum: The eigenvalues (and eigenvectors)
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.