Recent Publications

In social network analysis, the fundamental idea behind the notion of roles is to discover actors who have similar structural signatures. Actors performing the same role have similar behavioural and functional characteristics. Few examples of structural roles are bridge nodes, clique members and star centers. Role discovery involves partitioning the nodes in a network based on their structural characteristics. The notion of roles is complementary to the notion of community detection, which involves partitioning the network into cohesive subgroups. In this paper we propose a novel algorithm RID$\varepsilon$Rs (Role Identification and Discovery using $\varepsilon$-equitable Refinements): a graph partitioning approach for extracting soft roles in networks. RID$\varepsilon$Rs discovers structural roles based on the global graph characteristics of a network. Evaluating the quality of roles discovered is non-trivial due to the lack of ground-truth role datasets, we present a novel framework for evaluating and comparing various role discovery approaches. We also demonstrate the effectiveness of RID$\varepsilon$Rs on diverse graph mining tasks: role identification/discovery and for finding top-k nodes that are most similar to a given node. Further, the empirical scalability analysis of our proposed algorithm on random power-law graphs shows that our approach is highly scalable.
ICDE 2017

In social network analysis, the fundamental idea behind the notion of position is to discover actors who have similar structural signatures. Positional analysis of social networks involves partitioning the actors into disjoint sets using a notion of equivalence which captures the structure of relationships among actors. Classical approaches to Positional Analysis, such as Regular equivalence and Equitable Partitions, are too strict in grouping actors and often lead to trivial partitioning of actors in real world networks. An $\epsilon$-Equitable Partition ($\epsilon$EP) of a graph is an useful relaxation to the notion of structural equivalence which results in meaningful partitioning of actors. All these methods assume a single role per actor, actors in real world tend to perform multiple roles. For example, a Professor can possibly be in a role of "Advisor" to his PhD students, but in a role of "Colleague" to other Professors in his department. In this thesis we propose epsilon-equitable partitions based approaches to perform scalable positional analysis and to discover positions performing multiple roles. First, we propose and implement a new scalable distributed algorithm based on MapReduce methodology to find $\epsilon$EP of a graph. Empirical studies on random power-law graphs show that our algorithm is highly scalable for sparse graphs, thereby giving us the ability to study positional analysis on very large scale networks. Second, we propose a new notion of equivalence for performing positional analysis of networks using multiple epsilon-equitable partitions. These multiple partitions give us a better bound on identifying equivalent actor "positions" performing multiple "roles". Evaluation of our methods on multi-role ground-truth networks and time evolving snapshots of real world social graphs show the importance of epsilon equitable partitions for discovering positions performing multiple roles and in studying the evolution of actors and their ties.
MS by Research Thesis, IIT Madras

In social network analysis, the fundamental idea behind the notion of position and role is to discover actors who have similar structural signatures. Positional analysis of social networks involves partitioning the actors into disjoint sets using a notion of equivalence which captures the structure of relationships among actors. Classical approaches to Positional Analysis, such as Regular equivalence and Equitable Partitions, are too strict in grouping actors and often lead to trivial partitioning of actors in real world networks. An $\epsilon$-Equitable Partition ($\epsilon$EP) of a graph, which is similar in spirit to Stochastic Blockmodels, is a useful relaxation to the notion of structural equivalence which results in meaningful partitioning of actors. In this paper we propose and implement a new scalable distributed algorithm based on MapReduce methodology to find $\epsilon$EP of a graph. Empirical studies on random power-law graphs show that our algorithm is highly scalable for sparse graphs, thereby giving us the ability to study positional analysis on very large scale networks. We also present the results of our algorithm on time evolving snapshots of the facebook and flickr social graphs. Results show the importance of positional analysis on large dynamic networks.
SDM 2014

Contact

  • pratik[d . t]gupte[@]gmail.com