Indo-US Bilateral Workshop on Large Scale
Complex Network Analysis

 

---

Workshop Registration:

• Registration Link : http://www.cvent.com/d/brqg2m

• Early Registration Deadline: 09 November, 2015

---

Key Features:

• Eminent scientists from USA and India will deliver presentations
• Government and industry experts will give talks on the needs of the industry
• Various researchers from multi-disciplinary subjects ranging from Graph Theory, Algorithms, Statistics, Computer Networks, Data Science, Social Networking, etc. will participate in the panel discussions
• Great opportunity for Masters and Ph.D. students to learn about the current state-of-the art research

---

List of Speakers:
 

Y. Narahari IISC, Bangalore	Brigitte Jaumard Concordia University	Bimal K. Roy, ISI, Kolkata
Ananth Kalyanaraman School of EECS , Washington State University	Balaraman Ravindran IIT Madras	Niloy Ganguly IIT  Kharagpur
	Prasant Mohapatra University of California, Davis

 

---

About the Workshop:
 

Innovations in the next generation of network systems, together with explosive growth of the Web, Cloud and Mobile Computing, Big Data Science and Social Networking as well as Internet of Things, have resulted in a plethora of new applications and services. Various organizations, government agencies, and application service providers foresee that in the next few years, modeling and analysis of these kinds of large complex networks to achieve reliability, performance guarantee, robustness and security will be extremely important for both enterprises and end users. Hence, all these recent developments have created a great opportunity for Analysis of Large Scale Complex Networks.

In order to analyze large scale complex networks, a multidisciplinary approach is needed with techniques from computer networks, graph theory, distributed algorithms, social network analysis, and so on. Hence analysis of large scale complex networks poses significant challenges to the research community.

This bilateral workshop will serve as a platform to bring together leading researchers from academic institutions, R&D organizations, and practicing professionals from US and India for exchange of ideas and to discuss state-of-the-art approaches to important problems and disseminate results of current research. Another important role of this workshop will be to train and motivate students and research scholars to work in this area to build up a strong pool of researchers in coming days.

Talk Abstracts:

Keynote Speaker: Brigitte Jaumard, Concordia University, Topic: Enhanced RWA Solutions  for Very Large Data Instances

Abstract: While the Routing and Wavelength Assignment (RWA) has been widely studied, few studies attempt to solve realistic size instances, i.e., with 100 wavelengths and few hundred nodes. Indeed, state of the art is closer to around 20 nodes and 30 wavelengths, whether the authors consider heuristics or exact methods. In this paper, we are interested in reducing the gap between these two data instance sizes, using exact methods. Even if exact methods may fail to solve in reasonable time very large instances, they however output bounds on the accuracy of the heuristic solutions. The novelty of our work is to exploit the observations that optimal solutions contain a very large number of light-paths associated with a shortest path, and bottleneck links that prevent using shortest paths. We then propose different RWA algorithms that lead to solve exactly much larger instances than in the literature with up to 100 wavelengths and 40 nodes.

Keynote Speaker: Bimal Roy, Indian Statistical Institute, Topic: Data Obfuscation

Abstract. Data obfuscation is certain aspect of data security with focus on masking entity identities in large databases before public release of data. From the obfuscated data one may be able to compute certain functions of the original data, but cannot retrieve any individual information. A method of obfuscation is presented that will enable any user to estimate the statistical distribution of the original data.

Keynote Speaker: Y. Narahari, Topic: Mechanism Design for Strategic Crowdsourcing Networks for Geosensing Applications

Abstract: In several geosensing oriented crowdsourcing applications, for example, traffic monitoring, air pollution measurements, and epidemic monitoring, the structure of the tasks in space or time exhibits a natural special ordering. We model and analyze the problem of allocating a group of specially ordered crowdsourcing tasks, where it is natural for crowd workers to bid on a subset of contiguous tasks. If the crowd workers are heterogeneous (that is, with different levels of quality) and strategic (that is, maximizing their own individual utilities), the problems of task allocation and payment determination so as to achieve social welfare and cost minimization become non-trivial and even impossible. In this talk, we discuss the challenges involved in designing algorithmic mechanisms for such problems. The main contribution of our work is to propose a scalable approximation algorithm that runs in polynomial time and produces monotone allocations; we are able to provide theoretical guarantees on the approximation factor. We combine this algorithm with an appropriate payment scheme to develop a truthful and individually rational mechanism for task allocation in such problems.

Invited Talk: CEIL: A Scalable, Resolution Limit Free Approach for Detecting Communities in Large Networks, Speaker: Balaraman Ravindran, Indian Institute of Technology, Madras

Abstract. Real world networks typically exhibit non uniform edge densities with there being a higher concentration of edges within modules or communities. Various scoring functions have been proposed to quantify the quality of such communities. In this paper, we argue that the popular scoring functions suffer from certain limitations. We identify the necessary features that a scoring function should incorporate in order to characterize good community structure and propose a new scoring function, CEIL (Community detection using External and Internal scores in Large networks), which conforms closely with our characterization. We also demonstrate experimentally the superiority of our scoring function over the existing scoring functions.

Modularity, a very popular scoring function, exhibits resolution limit, i.e., one cannot find communities that are much smaller in size compared to the size of the network. In many real world networks, community size does not grow in proportion to the network size. This implies that resolution limit is a serious problem in large networks. Modularity is still very popular since it offers many advantages such as fast algorithms for maximizing the score, and non-trivial community structures corresponding to the maxima. We show analytically that the CEIL score does not suffer from resolution limit. We also modify the Louvain method, one of the fastest greedy algorithms for maximizing modularity, to maximize the CEIL score. We show that our algorithm gives the expected communities in synthetic networks as opposed to maximizing modularity. We also show that the community labels given by our algorithm matches closely with the ground truth community labels in real world networks. Our algorithm is on par with Louvain method in computation time and hence scales well to large networks.

Invited Talk: On Scaling Graph Algorithms for the New Age Biological Sciences, Speaker: Ananth Kalyanaraman, Washington State University

Abstract. Modern day life sciences present immense challenges and opportunities to theoreticians, algorithm developers, and application practitioners alike. In this talk, I will present an overview on some of the emerging topics within this rapidly evolving field, and a set of problems that motivate a compelling need for developing efficient graph methods. One such problem that we will discuss in detail is the problem of graph clustering, which has wide applications in computational genomics, transcriptomics and metagenomics. Another problem is the problem of graph construction. For both problems, I will present efficient parallel algorithms and heuristics that are designed to scale on a wide variety of parallel architectures including multi-core/many-core architectures and distributed memory machines. Time permitting, we will discuss some new venues for exploration in graph algorithm design and its application to modern day life sciences.

Invited Talk: Extracting Information from Microblogs during Disaster Events: A Classification-Summarization Approach, Speaker: Niloy Ganguly, IIT Kharagpur

Abstract. Microblogging sites like Twitter have become important sources of real-time situational information during disaster events. A large amount of valuable situational information is posted in these sites during disasters; however, this information is dispersed among hundreds of thousands of tweets containing sentiments and opinion of the masses. To effectively utilize microblogging sites during disaster events, we need a framework, which first classifies tweets to extract situational information, and then summarizes the information. On the other hand, non-situational tweets have different implications. For example, opinions/sentiments can be analyzed to track the perception of people, charity tweets can be propagated to a large number of audiences so that more people can contribute to relief funds. Besides that, communal tweets are also posted during such disaster events which can disrupt communal harmony and make the situation further worsen. It is also necessary to develop a classifier to separate out different non-situational tweets, and filter those communal tweets as early as possible which this project does.

Panel: State of the Art of Large Scale Complex Networks: Problems & Challenges,
Chair: Subhankar Dhar, San Jose State University,
Panelists: Brigitte Jaumard, Concordia University, Montreal, Ananth Kalyanaraman, Washtington State University,Pullman,  Prashant Mohapatra, University of California, Davis, Y.Narahari, Indian Institue of Science, Bangalore, Balaraman Ravindran, IIT Madras

Call for Abstracts: