Abstract

After several days of planning, the idea of a research retreat for our CNeRG Lab was finally realized. We broke off from the tensions and preoccupations about upcoming deadlines, reviews and seminars of day-to-day academic life to spend two days fully devoted to answering broader questions on the steadily-expanding CNeRG unit. How successful have we been? How self-reliant are we? Where do we see ourselves a year from now? The two days were spent seeking these answers and many more questions of introspection. It was, to say the least, a “roaring” success. The exuberance and zeal shown even by new members and otherwise introvert old members held testimony to that. Each of the participants presented his/her recent work to be scrutinized by the rest of the group. After close to sixteen hours of presentations split over two calendar days, it was unanimous that a careful peer-review of one’s research can be extremely useful for any graduate student. New members also came to know the story about the conception and evolution of the group over the last six-seven years. The frank analysis sessions presented by Prof. Niloy Ganguly and Prof. Animesh Mukherjee actually brought to light the reasons behind our successes and failures at top venues. Discussions also revolved around participation levels of external collaborators and our own intellectual contributions in collaborative research projects. The concluding mood was one of optimism, with the key realization being that increasing “synergy” within the group was the only way that CNeRG can continue being a self-sustaining and successful research group.

Participants

  • Prof. Niloy Ganguly
  • Prof. Animesh Mukherkee
  • Sourav Dandapat
  • Rajib Ranjan Maiti
  • Saptarshi Ghosh
  • Rishiraj Saha Roy
  • Sudipta Saha
  • Parantapa Bhattacharya
  • Tanmoy Chakraborty
  • Abir De
  • Sujoy Saha
  • Ratna Saha
  • Suman Kalyan Maity
  • Swadhin Pradhan
  • Souvik Sur
  • Sandipan Sikdar

Retreat 2012 snaps now available for download here!

Abstracts of Student Talks

Sprinkler: Distributed Content Storage for Just-in-time Streaming (Sourav Dandapat)

We envision cities where networking infrastructures, such as Wi-Fi access points (AP), will be equipped with storage capabilities. We propose to utilize the storages as a large distributed video cache. If successful, we envision that a child will be able to seamlessly watch a movie in a car, as her tablet downloads necessary parts of the movie over different Wi-Fi APs. The key challenge arises from the fact that the mobile tablet would not be able to download the entire movie from any single AP. Nonetheless, we show that the APs could be appropriately populated with video chunks, such that the tablet can always get the needed chunk, just-in-time for video playback. Thus, every video need not be replicated on every AP – our system minimizes replication of video chunks, offering citizens with far greater number of videos to watch. We believe that such a video service could benefit cellular networks, by offloading their traffic to a sizeable extent. This research takes a first step into exploring such a city-wide content distribution service, and addresses one piece of the puzzle – efficient content storage.

Online and Offline Socio-technological Networks (Saptarshi Ghosh)

This talk presented an overview of the studies in which I have been involved over the last three years. The studies were on (i) online socio-technological networks, specifically Online Social Networks (OSNs), and (ii) offline socio-technological networks, specifically the Indian Railway Network (IRN). We have studied various issues on OSNs, such as developing Complex Network Theoretic models for the evolution of the Twitter social network in the presence of cutoffs on node-degree, detecting overlapping communities in folksonomies (such as Delicious and Flickr), combating spam and link farming in Twitter, and improving topical search in Twitter. In case of the IRN, we have studied the network topology, the distribution of traffic in various routes and the run-time delay of trains. We have also investigated the possible factors behind the recent spate of accidents in Indian Railways.

Structural Complexity of Web Search Queries (Rishiraj Saha Roy)

It is believed that Web search queries are becoming more structurally complex over time. However, there has been no systematic study that quantifies these characteristics. Here, we take the first step towards understanding and characterizing the structural complexity of queries using a multipronged approach. We use traditional statistical language modeling techniques (n-grams) to quantify and compare the perplexity of queries with natural languages; we use complex network analysis again to quantify and compare the topological properties of queries and corresponding n-gram models with each other and against natural language; finally, we design experiments to study how well search engine users can tell apart real from generated queries. The three complementary approaches provide us with a holistic view of the structural complexity of queries which is more complex than what n-grams can capture, but yet more predictable than natural languages.

Alpha-bins and Evolution of Random Threshold Graphs (Sudipta Saha)

The one-mode projection of the alphabetic-bipartite networks has been analyzed in various ways in the literature. The degree distribution as well as various special properties of the same have been well explored. Even, the thresholded one-mode projection has been also the focus of few research. From the perspective of real life applications of the alphabetic-bipartite networks, a specific threshold value can be used to model the intensity of a certain constraint. Therefore, in case of the thresholded one-mode projection, prediction of the exact structure of the graph, is much important than the prediction of other generic / common metrics such as degree distribution or the component size distribution. In this work, we primarily focus on the prediction of the exact structure of the projection after application of a specific threshold value. We have found that, a thresholded one-mode projection graph can be represented as a random threshold-graph and therefore, there is a one-to-one correspondence between the set of possible configurations of the thresholded one-mode projections of alphabetic-bipartite network having N alphabetic-bins and the set of binary strings with N-1 bits. Exploiting this property, we intend to understand the whole evolution process through application of gradually increasing threshold values as well as identify the typical paths through which the evolution proceeds with high probability.

Community Formation and its Applications in Complex Networks (Tanmoy Chakraborty)

The presentation mainly deals with the two broad perspectives of my present experiments: community formations in complex networks and its intrinsic and extrinsic applications in complex network analysis. We know that when a certain network is subjected to various community algorithms, each of them produces different community configuration. Even for a particular algorithm, difference in initialization results in different configurations. However, our initial investigation shows that there are certain stable units (groups of nodes) which remain together independent of the algorithms used or the order in which an algorithm has been initialized. From this empirical observation we investigate the characteristic properties of these units, formulate a theoretical quantification to define a stable unit and use the quantification so formulated to devise community detection algorithms that are significantly faster and more accurate than the benchmark approaches. In the application point of view, we have investigates how the research communities of Computer Science domain evolve over the time, how their constant interactions in terms of the citations shape the universal research pattern and the probable reasons behind this research focus-shift. On the other hand, we are trying to build two recommendation systems with the help of prior community detection results: (i) paper recommendation system that hybridize the results of overlapping communities in citation network and the traditional collaborative filtering technique between users, and (ii) collaboration recommendation system that can suggest a list of possible collaborators with their ranks for an author based on the trust that has been built due to the transitive relationships between the co-authors over the years.

On Language Games (Suman Kalyan Maity)

This talk gives an brief overview of language games. In particular, it presents two such language games on which I am working on for past one and half years – i) Naming game ii) Category game. Naming game is a model of negotiation dynamics for the self-organized emergence of a linguistic convention or a communication system in a population of agents with pair-wise local interactions. The aim of this game is to agree on a name of an object. Agents can take part in this game as a speaker or a hearer and interact locally. These pairwise local interactions lead to “success” (locally agree on the name) or “failure” (the hearer learns the name) events and through a series of such events, the whole population come to an agreement on the name of the object. The other game (Category game) focuses on more complex task than naming, i.e, categorization. The category game is a minimal model for linguistic categorization. In the spirit of reducing the rich spectrum of linguistic phenomena to essential aspects, tractable to mathematical or numerical modeling, linguistic categorization is considered as the elaboration of a map between a large set of perceptions or concepts and a small set of linguistic labels, typically nouns or attributes. The paradigmatic case is offered by color naming: the potentially very large set of perceivable colors is mapped into a list of 5 – 10 basic color terms. The aim of the category game is not only reproducing in a realistic fashion the static (i.e., final) categorization pattern which is composed of a partition of the perceptual space and the dictionary connecting each category to a label, but to conjecture a plausible dynamics which brings to the light this final pattern in a large population of interacting individuals, all starting from an empty linguistic knowledge.

Landmarker: a bio-inspired Landmark Enumeration System for Localization (Swadhin Pradhan)

Nature has many invisible natural landmarks which are beyond the sensory capabilities of human being. Different creatures, like migratory birds, desert ants etc., use their capability to tap into these natural features for navigation. They use these natural characteristics as cues to find their destinations. Though human beings are intelligent, they are handicapped by their sensory limitations to see these natural cues, for localization in unknown environment. On the other hand, world has seen an unprecedented growth of different sensor enabled smart phones with advanced computing capability and connectivity. Our idea is that to use the sensory and computing capability of these mobile devices to find those invisible natural landmarks. We have developed an android application to get different sensor information at a specified sampling rate and an offline system to find different landmarks using clustering from this raw sensory data. We can use these landmarks in localization, prevention of location cheating and augmented reality applications.

Flow Analysis on Temporal Network (Souvik Sur)

The well-known Max-Flow Problem in Temporal Network. Max-Flow problem is already defined and solved efficiently in static network.But, in Temporal Network, it isn’t even defined properly while Temporal Network Model captures many real life network better than Static Network Model. So,in this talk, I discussed about the Max-Flow problem in Static Network, extending the same concept into the Temporal Network to properly define the problem.

Last updated: January 02, 2013