Spectral Techniques for Heterogeneous Social Networks

Abstract

Social networks represent a set of participants and the pairwise relationships between them. There are several different types of networks, such as directed networks, networks with typed edges, dynamic networks and signed networks, as well as composition of different types of networks. Each individual behaves in certain ways in particular situations. Each social situation could represent a status over a time interval for a dynamic network or a specific relationship or role, such as a working relationship or friendship in a network with typed edges, or an incoming role or outgoing role in a directed network.

In much social network analysis, edges are only positively weighted, and also of a single type. Ignoring the qualitative differences of relationships rules out several interesting kinds of analysis. I develop a novel way to analyze such networks by considering the qualitatively different social roles that each individual can play in a network. Each individual is represented by copies corresponding to the roles.

Each role or status and the corresponding connections define a subgraph. I model the subgraph as a layer, and show how to weight the edges connecting the layers to produce a consistent spectral embedding. This embedding can be used to compute social network properties of graphs of different types, to predict edges, edge types, and edge direction, as well as to track the change of role over time. I illustrate the approaches using synthetic and real-world datasets.

Furthermore, conventional Laplacian approaches are designed for graphs with positively weighted edges and do not deal with signed graphs, which have positively and negatively weighted edges. I derive spectral analysis methods for signed graphs and extend the methods for graph based semi-supervised learning. Using real-world data, I show that they produce robust results.