By Karthika Swamy Cohen
Biological, social, and information networks all form complex networks, which are made of interconnected nodes. As networks increase in size and complexity, so does the research associated with them.
One key area of study is community structure and detection. The increasing availability of data sets of large-scale networks has inspired growing interest in community detection, which is essential to understand the functionality of complex networks. Community and role detection within networks have broad applications.
At the SIAM Annual Meeting being held in Portland, Ore. this week, Carlotta Domeniconi of George Mason University described the significance of roles in online communities in a minisymposium talk titled Finding Communities and Roles in Networks.
A scientific collaboration network. The nodes represent scientists and the links represent collaborations among them. Image credit: Mark Newman.
User contribution and participation are essential features of online social networks, which require users to perform specific activities and adopt defined roles. Domeniconi proposed a new methodology for discovering such roles in social networks, which can shed light on the overall working of online communities.
The methodology assumes that a community is a sub graph. But graphs are not static objects. They are dynamic, Domeniconi explained, so they must account for changes. “People change over time, change interests, shift focus from one community to another,” she observed. Also, their resources and time are limited. “If I'm interested in coffee I'm also interested in computer science, but my day is limited to 24 hours.”
Network detection must factor in this nature of dynamic networks. In a social network, nodes depict people and edges represent interactions between people. Recurrent interactions are represented by directed edges, which are weighted to show the number of times an interaction was performed. People in networks engage in particular actions, and take on specific roles. Roles can impart very different structural positions to users of online social networks.
How does one define a role? How do we discover roles of nodes in a network and latent role behaviors? Defining such behaviors permit compact representations of networks and are helpful in understanding temporal patterns of node behavior.
Do roles persist over time? How do users’ roles change over time? Do various networks have the same roles.
Identifying a set of roles common to multiple online social networks allows ways to perform comparative analyses among networks, thus emphasizing relationships between roles.
To answer the aforementioned questions, Domeniconi’s group compared data obtained from two networks: Facebook and Scratch, an online community that allows users to program interactive stories, games, and animations and share them with other users. The researchers used their methods to discover and trace persistent roles over time in the two data sets.
Communities may grow and shrink over time – members may join or leave networks. Edges die as people become inactive. In network analysis, it is important to avoid accumulation of inactive edges as this results in artifacts leading to inaccurate results.
To account for the dynamic nature of networks and to capture these snapshots, Domeniconi’s method partitions time into intervals and captures only active edges within each timeframe. This yields temporal snapshots for a given network.
Two networks of machine learning researchers with different concentrations.
Her group analyzed 26 network snapshots of online social networks from the two datasets. They then reviewed roles in the two networks by defining a set of 12 features to capture structural features of nodes, such as in-degree and out-degree, and interaction factors like reciprocity and social strategy.
Each node is thus represented as a 12-dimensional vector in this feature space. The researchers decomposed this matrix into two standard matrices and used standard algebra for matrix characterization. The discovered roles are determined by the resulting basis vectors. The role vectors contain values corresponding to each feature which help characterize the role. If a feature is highly expressed for a given role, it is assumed to be a feature more characteristic of the role. For example, if in-degree is particularly high for a role, one would presume it to be a popular role since there are lots of in edges coming to it.
After analyzing the data, Domeniconi found six roles persistent across all snapshots and common to both networks; these are: popular, friendly, explorer, reciprocated, community member, and active-community member. Her team then proceeded to analyze how the roles may help interpret network structure by studying role membership, transition, and interaction preferences. The main difference they determined was in how the roles evolved and how people changed over time.
While the discovered roles are distinct from each other, common to both datasets, and persist over time, researchers found differences in the relationships between roles. They conclude that common roles shared among social networks are beneficial to model and analyze networks.
 |
Karthika Swamy Cohen is the managing editor of SIAM News.
|