Pratik Gupte

Jump to: navigation, search

Programme: MS
Guide: Dr. B. Ravindran

Role Discovery in Social Networks

In social network analysis, role discovery involves partitioning the actors in a network into disjoint sets using a notion of equivalence which captures the structure of relationships among actors. The notion of roles differs significantly from that of communities, a popular way to organize actors in a network. A community consists of a set of nodes that have more links among themselves than to other nodes in the network. A role consists of nodes having similar structural signature, such as, broker nodes, clique members, star centers and near isolates. Nodes playing the same role are typically spread across the network and need not even be in the same component of the network. Our proposed approaches discover structural roles based on the complete structural view of a graph, hence do not require local node characteristics to be defined or computed a priori as with some of the existing role discovery algorithms.

The focus of my research work has been on the following two problems:

  1. MεEPs - Soft Role Discovery using Multiple ε-Equitable Partitions.
  2. Scalable Role Discovery in Networks.

Soft Roles (MεEPs)

  1. Key Contributions of MεEPs:
    1. MεEPs takes into account the complete structural view of the graph for computing the roles.
    2. MεEPs is scalable to large sparse graphs.
    3. Given the soft roles memberships of actors, MεEPs categorizes the actors into equivalence classes or positions.
    4. Validation of the roles and positions with multi-role ground-truth network datasets.

Scalable Role Discovery

  1. Scalable Positional Analysis for Studying Evolution of Nodes in Networks. In the Workshop on Mining Networks and Graphs: A Big Data Analytic Challenge, at the SIAM Conference on Data Mining (SDM 14).
  2. Key Contributions:
    1. Highly scalable for large sparse graphs. The latest implementation (details are yet to be published) is capable of handling graphs with half a billion edges on a single high end machine.
    2. Tool for studying node & link evolution characteristics in time evolving networks.
    3. Exploratory & visual analysis tool for dynamic networks.

This work opens up the study of roles in large social networks.

EMail: pratik[.]gupte[@]gmail[.]com Flickr:

Personal tools