what-when-how
In Depth Tutorials and Information
4.1 Introduction
Many natural and social systems develop complex networks; for example, the
Internet, the World Wide Web, networks of collaborating movie actors and those
of collaborating authors, etc. he management and analysis of these networks have
attracted increasing interest in the sociology, database, data mining, and theory
communities. Most previous studies are focused on revealing interesting properties
(e.g., degree sequences, shortest connecting paths, power-law degree distributions,
small-world phenomenon, and clustering coefficients) of networks and discovering
efficient and effective analysis methods [2-4, 9, 13, 15, 19, 21, 22, 24, 30, 33, 34,
36, 39].
In this chapter we analyze social networks from a spectrum point of view. Graph
spectral analysis deals with the analysis of the spectra (eigenvalues and eigenvec-
tor components) of the graph's adjacency matrix or other derived matrices. he
spectrum of a graph is usually defined as the set of eigenvalues of the graph. It has
been shown that there is an intimate relationship between the combinatorial char-
acteristics of a graph and the algebraic properties of its adjacency matrix [30]. Our
graph spectral analysis centers on two applications: graph randomness analysis and
graph perturbation.
Social networks tend to contain some amount of randomness and some
amount of nonrandomness. Consider an online social network where each node
denotes an individual, and an edge between two nodes denotes a social interac-
tion between the two individuals. An individual's social network tends to consist
of members of the same ethnic group, race, or social class. Intuitively, two friends
of a given individual are more likely to be friends with each other than they
are with other randomly chosen members. he edge connecting one individual's
two friends contains less randomness. However, an individual also tends to have
some number of random friends from other groups, and those edges between
this individual and his random friends contain more randomness. he amount of
randomness versus nonrandomness at node/edge levels can clearly affect various
properties of a social network. Although randomness plays an important role in
understanding the geometry and topology of social networks, very few studies
have formally investigated this issue. In this paper, we theoretically analyze graph
randomness and present a framework that provides a series of nonrandomness
measures at levels of edge, node, and the overall graph. We show that graph non-
randomness can be obtained mathematically from the spectra of the adjacency
matrix of the network. We conduct both theoretical and empirical studies in
spectral geometries of social networks and show that our proposed nonrandom-
ness measures can better characterize and capture graph randomness than previ-
ous measures.
Many applications of networks such as anonymous Web browsing require
relationship anonymity due to the sensitive, stigmatizing, or confidential nature
of relationships. he privacy concerns associated with data analysis over social
