SEMINAR TALK ARCHIVE


Spring '11 |Fall '10 |Summer '10 |Spring '10 | Fall '09 | Summer '09 | Spring '09 | Fall '08Spring '08 | Fall '07 | Summer '07 | Spring '07

Spring '11

 


 

Date: April 26, 2011
Presentor: Ying Xuan
Paper Title: Social Influence Analysis in Large-scale Networks
Slides Link:
[PPT]

Abstract:

In large social networks, nodes (users, entities) are influenced by others for various reasons. For example, the colleagues have strong influence on one’s work, while the friends have strong influence on one’s daily life. How to differentiate the social influences from different angles(topics)? How to quantify the strength of those social influences? How to estimate the model on real large networks? To address these fundamental questions, we propose Topical Affinity Propagation (TAP) to model the topic-level social influence on large networks. In particular, TAP can take results of any topic modeling and the existing network structure to perform topic-level influence propagation. With the help of the influence analysis, we present several important applications on real data sets such as 1) what are the representative nodes on a given topic? 2) how to identify the social influences of neighboring nodes on a particular node? To scale to real large networks, TAP is designed with efficient distributed learning algorithms that is implemented and tested under the Map-Reduce framework. We further present the common characteristics of distributed learning algorithms for Map-Reduce. Finally, we demonstrate the effectiveness and efficiency of TAP on real large data sets.



Date: April 19, 2011
Presentor: Linna Wei
Paper Title: A tight bound on approximating arbitrary metrics by tree metrics
Slides Link:
[PPT]

Abstract:

In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Ω(log n)-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.


Date: April 12, 2011
Presentor: Thang N. Dinh
Paper Title: A Unified Approach for Domination Problems on Different Network Topologies
Slides Link:
[PPT]

Abstract:

We provide tight hardness results and approxiamation algorithms for many existing domination problems. We start with the \emph{positive influence dominating set} (PIDS) problem, originated from the context of influence propagation in social networks. The PIDS problem seeks for a minimal set of nodes $\mathcal{P}$\ such that all other nodes in the network have at least a fraction $\rho > 0$\ of their neighbors in $\mathcal{P}$; in the \emph{total} version (T-PIDS), nodes in $\mathcal{P}$\ are required to have a fraction $\rho$\ of neighbors inside $\mathcal{P}$; and in the \emph{connected} version (C-PIDS) the dominating set have to induce a connected subgraph. Then, we unify a large variations of dominating set problem under a single generalized dominating set problem. We show a tight hardness results $\frac{1}{2}(1- o(1))\ln n$ inapproximability and a $\ln \Delta + O(1)$ approximation algorithms for our generalized dominating set problem where $n$ is the newtork size and $\Delta$ is the maximum degree. The results apply directly to PIDS, $k$-tuple dominating set, $m$-connected $k$-dominating set, Fixed Threshold Dominating Set and many existing domination problems plus all connected or/and total versions of those problems. As most previous hardness results are NP-completeness or APX-hardness, we effectively close many long-standing approximation gaps of domination problems, under the reasonable assumption that NP $\not \subset$ DTIME($n^{O(\log \log n)}$). In networks with degrees bounded by a constant $B$, we show that all problems cannot be approximated within $\ln B - O\left(\ln \ln B\right)$, unless P=NP. In dense networks and scale-free networks such as Internet, WWW, social networks, etc. in which degree sequences follows a power-law distribution, we reveal trivial constant factor approximation algorithms for the class of PIDS-like domination problems. Finally, we prove that optimal solution of any domination problems can be found in linear time for networks with tree topology.


Date: April 5, 2011
Presentor: Xincen Yu
Paper Title: Sybil Attacks Against Mobile Users: Friends and Foes to the Rescue
Slides Link:
[PDF]

Abstract:

Collaborative applications for co-located mobile users can be severely disrupted by a sybil attack to the point of being unusable. Existing decentralized defences have largely been designed for peer-to-peer networks but not for mobile networks. That is why we propose a new decentralized defence for portable devices and call it MobID. The idea is that a device manages two small networks in which it stores information about the devices it meets: its network of friends contains honest devices, and its network of foes contains suspicious devices. By reasoning on these two networks, the device is then able to determine whether an unknown individual is carrying out a sybil attack or not. We evaluate the extent to which MobID reduces the number of interactions with sybil attackers and consequently enables collaborative applications.We do so using real mobility and social network data. We also assess computational and communication costs of MobID on mobile phones.


Date: March 29, 2011
Presentor: Nam P. Nguyen
Paper Title: MetaFac: community discovery via relational hypergraph factorization
Slides Link:
[PPT]

Abstract:

This paper aims at discovering community structure in rich media social networks, through analysis of time-varying, multi-relational data. Community structure represents the latent social context of user actions. It has important applications in information tasks such as search and recommendation. Social media has several unique challenges. (a) In social media, the context of user actions is constantly changing and co-evolving; hence the social context contains time-evolving multi-dimensional relations. (b) The social context is determined by the available system features and is unique in each social media website. In this paper we propose MetaFac (MetaGraph Factorization), a framework that extracts community structures from various social contexts and interactions. Our work has three key contributions: (1) metagraph, a novel relational hypergraph representation for modeling multi-relational and multi-dimensional social data; (2) an efficient factorization method for community extraction on a given metagraph; (3) an on-line method to handle time-varying relations through incremental metagraph factorization. Extensive experiments on real-world social data collected from the Digg social media website suggest that our technique is scalable and is able to extract meaningful communities based on the social media contexts. We illustrate the usefulness of our framework through prediction tasks. We outperform baseline methods (including aspect model and tensor analysis) by an order of magnitude.


Date: March 22, 2011
Presentor: Yu-Song Syu
Paper Title: Item-based Collaborative Filtering Recommendation Algorithms
Slides Link:
[PPT]

Abstract:

Recommender systems apply knowledge discovery techniques to the problem of making personalized recommendations for information, products or services during a live interaction. These systems, especially the k-nearest neighbor collaborative filtering based ones, are achieving widespread success on the Web. The tremendous growth in the amount of avail- able information and the number of visitors to Web sites in recent years poses some key challenges for recommender sys- tems. These are: producing high quality recommendations, performing many recommendations per second for millions of users and items and achieving high coverage in the face of data sparsity. In traditional collaborative filtering systems the amount of work increases with the number of partici- pants in the system. New recommender system technologies are needed that can quickly produce high quality recommendations, even for very large-scale problems. To address these issues we have explored item-based collaborative filtering techniques. Item-based techniques first analyze the user-item matrix to identify relationships between different items, and then use these elationships to indirectly compute recommendations for users. In this paper we analyze different item-based recommen- dation generation algorithms. We look into different techniques for computing item-item similarities (e.g., item-item correlation vs. cosine similarities between item vectors) and different techniques for obtaining recommendations from them (e.g., weighted sum vs. regression model). Finally, we experimentally evaluate our results and compare them to the basic k-nearest neighbor approach. Our experiments suggest that item-based algorithms rovide dramatically better performance than user-based algorithms, while at the same time providing better quality than the best available user- based algorithms.


Date: March 15, 2011
Presentor: Sindhura Tokala
Paper Title: Correcting for Missing Data in Information Cascades
Slides Link:
[PDF]

Abstract:
Transmission of infectious diseases, propagation of information, and spread of ideas and influence through social networks are all examples of diffusion. In such cases we say that a contagion spreads through the network, a process that can be modeled by a cascade graph. Studying cascades and network diffusion is challenging due to missing data. Even a single missing observation in a sequence of propagation events can significantly alter our inferences about the diffusion process. We address the problem of missing data in information cascades. Specifically, given only a fraction C′ of the complete cascade C, our goal is to estimate the properties of the complete cascade C, such as its size or depth. To estimate the properties of C, we first formulate k-tree model of cascades and analytically study its properties in the face of missing data. We then propose a numerical method that given a cascade model and observed cascade C′ can estimate properties of the complete cascade C. We evaluate our methodology using information propagation cascades in the Twitter network (70 million nodes and 2 billion edges), as well as information cascades arising in the blogosphere. Our experiments show that the k-tree model is an effective tool to study the effects of missing data in cascades. Most importantly, we show that our method (and the k-tree model) can accurately estimate properties of the complete cascade C even when 90% of the data is missing.


Date: March 1, 2011
Presentor: Yilin Shen
Paper Title: Approximation Algorithms and Hardness for Domination with Propagation
Slides Link:
[PDF]

Abstract:
The power dominating set (PDS) problem is the following extension of the well-known dominating set problem: find a smallest-size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or v has a neighbor in S, or (2) v has a neighbor w such that w and all of its neighbors except v are power dominated. Note that rule (1) is the same as for the dominating set problem, and that rule (2) is a type of propagation rule that applies iteratively. We use n to denote the number of nodes. We show a hardness of approximation threshold of 2log1−n in contrast to the logarithmic hardness for dominating set. This is the first result separating these two problem. We give an O(n) approximation algorithm for planar graphs, and show that our methods cannot improve on this approximation guarantee. We introduce an extension of PDS called ℓ-round PDS; for ℓ= 1 this is the dominating set problem, and for ℓ ≥ n − 1 this is the PDS problem. Our hardness threshold for PDS also holds for ℓ-round PDS for all ℓ≥4. We give a PTAS for the ℓ-round PDS problem on planar graphs, for =O(lognloglogn) . We study variants of the greedy algorithm, which is known to work well on covering problems, and show that the approximation guarantees can be Θ(n), even on planar graphs. Finally, we initiate the study of PDS on directed graphs, and show the same hardness threshold of 2log1−n for directed acyclic graphs.


Date: Feburary 22, 2011
Presentor: Dung T. Nguyen
Paper Title: Community-based greedy algorithm for mining top-K influential nodes in mobile social networks
Slides Link:
[PPT]

Abstract:
With the proliferation of mobile devices and wireless technologies, mobile social network systems are increasingly available. A mobile social network plays an essential role as the spread of information and influence in the form of "word-of-mouth". It is a fundamental issue to find a subset of influential individuals in a mobile social network such that targeting them initially (e.g. to adopt a new product) will maximize the spread of the influence (further adoptions of the new product). The problem of finding the most influential nodes is unfortunately NP-hard. It has been shown that a Greedy algorithm with provable approximation guarantees can give good approximation; However, it is computationally expensive, if not prohibitive, to run the greedy algorithm on a large mobile network. In this paper we propose a new algorithm called Communitybased Greedy algorithm for mining top-K influential nodes. The proposed algorithm encompasses two components: 1) an algorithm for detecting communities in a social network by taking into account information diffusion; and 2) a dynamic programming algorithm for selecting communities to find influential nodes. We also provide provable approximation guarantees for our algorithm. Empirical studies on a large real-world mobile social network show that our algorithm is more than an order of magnitudes faster than the state-of-the-art Greedy algorithm for finding top-K influential nodes and the error of our approximate algorithm is small.


Date: Feburary 15, 2011
Presentor: Ying Xuan
Paper Title: A Sybil-proof One-hop DHT
Slides Link:
[PPT]

Abstract:
Decentralized systems, such as structured overlays, are subject to the Sybil attack, in which an adversary creates many false identities to increase its influence. This paper describes a one-hop distributed hash table which uses the social links between users to strongly resist the Sybil attack. The social network is assumed to be fast mixing, meaning that a random walk in the honest part of the network quickly approaches the uniform distribution. As in the related SybilLimit system [25], with a social network of n honest nodes and m honest edges, the protocol can tolerate up to o(n/log n) attack edges (social links from honest nodes to compromised nodes). The routing tables contain O(\sqrt{m log m}) entries per node and are constructed efficiently by a distributed protocol. This is the first sublinear solution to this problem. Preliminary simulation results are presented to demonstrate the approach’s effectiveness.


Date: Feburary 8, 2011
Presentor: Linna Wei
Paper Title: Energy-Balanced Dispatch of Mobile Sensors in a Hybrid Wireless Sensor Network
Slides Link:
[PPT]

Abstract:
We consider a hybrid wireless sensor network with static and mobile nodes. Static sensors monitor the environment and report events occurring in the sensing field. Mobile sensors are then dispatched to visit these event locations to conduct more advanced analysis. A big challenge is how to schedule these mobile sensors' traveling paths in an energy-balanced way so that their overall lifetime is maximized. We formulate this problem as a multiround sensor dispatch problem and show it to be NP-complete. Then, we propose a centralized and a distributed heuristics to schedule mobile sensors' traveling paths. Our heuristics allow arbitrary numbers of mobile sensors and event locations in each round and have an energy-balanced concept in mind. The centralized heuristic tries to minimize mobile sensors' moving energy while keeping their energy consumption balanced. The distributed heuristic utilizes a grid structure for event locations to bid for mobile sensors. Through simulations, we show the effectiveness of our schemes. This paper contributes in defining a more general multiround sensor dispatch problem and proposing energy-efficient solutions to it.


Date: January 25, 2011
Presentor: Thang N. Dinh
Paper Title: Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
Slides Link:
[PPT]

Abstract:
To comprehend the hierarchical organization of large integrated systems, we introduce the hierarchical map equation that reveals multilevel structures in networks. In this information-theoretic approach, we exploit the duality between compression and pattern detection; by compressing a description of a random walker as a proxy for real flow on a network, we find regularities in the network that induce this system-wide. Finding the shortest multilevel description of the random walker therefore gives us the best hierarchical clustering of the network | the optimal number of levels and modular partition at each level | with respect to the dynamics on the network. With a novel search algorithm, we extract and illustrate the rich multilevel organization of several large social and biological networks. For example, from the global air tra c network we uncover countries and continents, and from the pattern of scientific communication we reveal more than 100 scientific fields organized in four major disciplines: life sciences, physical sciences, ecology and earth sciences, and social sciences. In general, we find shallow hierarchical structures in globally interconnected systems, such as neural networks, and rich multilevel organizations in systems with highly separated regions, such as road networks.


Date: January 18, 2011
Presentor: Nam P. Nguyen
Paper Title:The Community-search Problem and How to Plan a Successful Cocktail Party
Slides Link:
[PDF]

Abstract:
A lot of research in graph mining has been devoted in the discovery of communities. Most of the work has focused in the scenario where communities need to be discovered with only reference to the input graph. However, for many interesting applications one is interested in finding the community formed by a given set of nodes. In this paper we study a query-dependent variant of the community-detection problem, which we call the community-search problem: given a graph G, and a set of query nodes in the graph, we seek to find a subgraph of G that contains the query nodes and it is densely connected.


Date: January 11, 2011
Presentor: Yu-Song Syu
Paper Title: New Approace to Quantification of Privacy on Social Network Sites
Slides Link:
[PPT]

Abstract:
Users may unintentionally reveal private information to the world on their blogs on social network sites (SNSs). Information hunters can exploit such disclosed sensitive information for the purpose of advertising, marketing, spamming, etc. We present a new metric to quantify privacy, based on probability and entropy theory. Simply by relying on the total leaked privacy value calculated with our metric, users can adjust the amount of information they reveal on SNSs. Previous studies focused on quantifying privacy for purposes of data mining and location finding. The privacy metric in this paper deals with unintentional leaks of information from SNSs. Our metric helps users of SNSs find how much privacy can be preserved after they have published sentences on their SNSs. It is simple, yet precise, which is proved through an experimental evaluation.

 

Fall '10

 


Date: December 6, 2010
Presentor: Sindhura Tokala
Paper Title: Stealing Reality
Slides Link:
[PPT]

Abstract:
In this paper we discuss the threat of malware targeted at extracting information about the relationships in a real-world social network as well as characteristic information about the individuals in the network, which we dub Stealing Reality. We present Stealing Reality, explain why it differs from traditional types of network attacks, and discuss why its impact is significantly more dangerous than that of other attacks. We also present our initial analysis and results regarding the form that an SR attack might take, with the goal of promoting the discussion of defending against such an attack, or even just detecting the fact that one has already occurred. The background information for this paper is available at another paper titled Inferring Social Network Structure using Mobile Phone Data.


Date: November 29, 2010
Presentor: Yilin Shen
Paper Title: Predicting Positive and Negative Links in Online Social Networks
Slides Link:
[PPT]

Abstract:
We study online social networks in which relationships can be either positive (indicating relations such as friendship) or negative (indicating relations such as opposition or antagonism). Such a mix of positive and negative links arise in a variety of online settings; we study datasets from Epinions, Slashdot and Wikipedia. We find that the signs of links in the underlying social networks can be predicted with high accuracy, using models that generalize across this
diverse range of sites. These models provide insight into some of the fundamental principles that drive the formation of signed links in networks, shedding light on theories of balance and status from social psychology; they also suggest social computing applications by which the attitude of one user toward another can be estimated from evidence provided by their relationships with other members of the surrounding social network.


Date: November 15, 2010
Presentor: Dung Nguyen
Paper Title: Wireless Array Based Sensor Relocation in Mobile Sensor Networks
Slides Link:
[PPT]

Abstract:
Mobility enables numerous functionalities in wireless sensor networks (WSN’s) including coverage optimization, network self-healing and adaptive resource management. In this paper, a novel wireless array-based sensor relocation (WASR) algorithm is proposed based on the cooperative sensing model, WA-CSM, presented in [4]. The WA-CSM model improves the network sensing coverage by utilizing closely located sensors upon deployment to form wireless arrays (WA’s). A Local Detection Diagram (LDD) is introduced as an important tool for local coverage hole detection. To increase the coverage, WA’s relocate the redundant nodes located within their coverage to suitable positions, while other sensors autonomously determine their own moving strategies.
The proposed algorithm runs iteratively and in a distributed fashion. It terminates naturally when the optimum coverage is achieved within the maximum moving distance allowed. As enhancements to the WA-SR algorithm, selfdetection and sensor movement-validation schemes are also proposed in this work. The effectiveness of the proposed approach is examined under various scenarios and supported by computer simulation studies.


Date: November 8, 2010
Presentor: Ying Xuan
Paper Title: Jamming-Aware Traffic Allocation for Multiple-Path Routing Using Portfolio Selection
Slides Link:
[PPT]

Abstract:
Multiple-path source routing protocols allow a data source node to distribute the total traffic among available paths. In this paper, we consider the problem of jamming-aware source routing in which the source node performs traffic allocation based on empirical jamming statistics at individual network nodes. We formulate this traffic allocation as a lossy network flow optimization problem using portfolio selection theory from financial statistics. We show that in multisource networks, this centralized optimization problem can be solved using a distributed algorithm based on decomposition in network utility maximization (NUM). We demonstrate the network's ability to estimate the impact of jamming and incorporate these estimates into the traffic allocation problem. Finally, we simulate the achievable throughput using our proposed traffic allocation method in several scenarios.


Date: November 1, 2010
Presentor: Nam Nguyen
Paper Title: Parallel community detection on large networks with propinquity dynamics
Slides Link:
[PPT]

Abstract:
Graphs or networks can be used to model complex systems. Detecting community structures from large network data is a classic and challenging task. In this paper, we propose a novel community detection algorithm, which utilizes a dynamic process by contradicting the network topology and the topology-based propinquity, where the propinquity is a measure of the probability for a pair of nodes involved in a coherent community structure. Through several rounds of mutual reinforcement between topology and propinquity, the community structures are expected to naturally emerge. The overlapping vertices shared between communities can also be easily identified by an additional simple postprocessing. To achieve better efficiency, the propinquity is incrementally calculated. We implement the algorithm on a vertex-oriented bulk synchronous parallel(BSP) model so that the mining load can be distributed on thousands of machines. We obtained interesting experimental results on several real network data.


Date: October 25, 2010
Presentor: Donatella Granata
Paper Title: Critical path detection

Abstract:
In the design and maintenance of any infrastructure networks, such as communication, commercial, transportation and social networks, plays a vital role a pre-active evaluation of possible diseases in order to considerate and avoid the decline of the network quality of service or even breakdown the whole network. From the physical point of view, a transportation network is a system of vehicular flows. Furthermore, we can state that it is a non-equilibrium system of interacting particles-vehicles. The instability of the free flow state (implying a non-altering standard speed) is caused by recurrent and non-recurrent congestion appearing in the edges of the transportation network. We introduce and formulate a Critical Path Detection problem, where a critical path is defined as the path between a source and a destination node whose deletion results in minimizing the size of any connected component. More specifically, in a transportation network, we define a critical path as a path that consists of links that, in case of heavy congestion conditions, divide the network and cause it to become fragmented and unreliable. Furthermore, when special events occur, (i.e., football game, concert, manifestations, etc)  it is necessary to consider the critical  paths  between hubs, that require special attention during the event in order to avoid backbone failures and “ paralyze” the vehicle circulation. As well, in evacuation networks, it is crucial to be able to estimate the amount of resources, goods transportation and evacuation places in order to offer a shelter for all the people involved in the disaster. Identifying  the critical path will help to planning the allocation and transport during the evacuation.


Date: October 18, 2010
Presentor: Linna Wei
Paper Title: Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms
Slides Link:
[PPT]

Abstract:
The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, two-dimensional discrepancy problems, and testing pseudorandom  number generators. However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem. The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2-dimensional bin packing. More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimensional bin packing and dynamic allocation.
In this paper, we solve the minimax grid matching problem and the maximum up-right matching problem. As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional pin packing, 1-dimensional on-line packing and on-line dynamic allocation. The results also solve  a long-open question in mathematical statistics.


Date: October 11, 2010
Presentor: Yu-Song Syu
Paper Title: Human Computation
Slides Link:
[PPT]

Abstract:
Human Computation (HCOMP), pioneered by Dr. Luis Von Ahn (CMU), ‘outsources’ certain steps of the computational process to humans to solve problems that computer computation has not been able to resolve completely thus far, such as image annotation and commonsense reasoning. The Games With A Purpose (GWAP) is a representative example. By taking advantage of people's desire to be entertained and exploiting "human cycles" in computation, the GWAP attracts people to play voluntarily, and also produce useful data as a by-product. In recent years, several GWAP systems have been developed for different purposes, and an increasing amount of research effort has been invested in the area. This presentation mainly consists of two
analytical works, whose “purposes” are geo-tagging and image annotation respectively, and which are both implemented as Internet GWAPs. In these works, we propose a model to analyze user behaviors, introduce a novel approach to improve the system performance, and then conduct metrics to evaluate the proposed methods under different circumstances with simulation and real data traces.


Date: October 04, 2010
Presentor: Chrysafis Vogiatzis
Paper Title: Vehicle Routing Problems: Extensions using Sensor-Based Optimization

Abstract:
Vehicle routing has been one of the modern stories of success in optimization. An NP-hard problem that was considered unsolvable by many researchers in the 1960s is now easily tractable and solved by several commercial and non-commercial software for large scale real-life problems. However, the real problem arises due to the uncertain and the continuous-time nature of the VRP. We propose a sensor-based algorithm with augmented Lagrange relaxation in order to approximately solve large scale instances on-the-fly.


Date: September 20, 2010
Presentor: Thang Dinh
Paper Title: Undirected s-t connectivity is in log space - A collapse of a complexity class
Slides Link:
[PDF]

Abstract:
We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3 obtained by Armoni, Ta-Shma, Wigderson and Zhou [9]. As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov [45] has presented an O(log n log log n)-space, deterministic algorithm for undirected st-connectivity.Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labelling and log-space constructible universal-exploration sequences for general graphs.


Date: September 09, 2010
Presentor: Ying Xuan
Paper Title: Adaptive Jamming-Resistant Broadcast Systems with Partial Channel Sharing
Slides Link:
[PPT]

Abstract:
Wireless communication is particularly vulnerable to signal jamming attacks. Spread spectrum mitigates such problem by spreading normal narrow band signals over a much wider band of frequencies and forcing jammers who do not know such spread pattern to invest much more effort to launch attacks.However, in broadcast systems, jammers can easily find out the spread pattern by compromising some receivers. Several group-based approaches have been proposed to deal with insider jammers who can compromise receivers in broadcast systems; they can tolerate t malicious receivers as long as the system can afford 2t additional copies for each broadcast message. This paper introduces a novel jamming-resistant broadcast system that organizes receivers into multiple channel-sharing broadcast groups and isolates malicious receivers using adaptive re-grouping. By letting receivers in different groups partially share their channels, this scheme reduces the extra communication cost from 2t to(2 − \rho)t copies, where \rho is the channel sharing factor (0<\rho<1); this is much closer to optimal given the previously proven lower bound of t additional copies. In addition, a sequential test based scheme is also proposed to further improve the performance so that \rho can be set larger to save more communication cost without reducing security. The analytic and simulation results show that the proposed approaches greatly push limit of jamming-resistant broadcast towards optimal.


Date: September 02, 2010
Presentor: Dung  T. Nguyen
Paper Title: Computing Best Coverage Path in the Presence of Obstacles in a Sensor Field
Slides Link:
[PDF]

Abstract:
We study the presence of obstacles in computing BCP(s, t) (Best Coverage Path between two points s and t) in a 2D field under surveillance by sensors. Consider a set of m line segment obstacles andn point sensors on the plane. For any path between s to t, p is the least protected point along the path such that the Euclidean distance between p and its closest sensor is maximum. This distance (the path’s cover value) is minimum for a BCP(s, t). We present two algorithmic results. For opaque obstacles, i.e., which obstruct paths and block sensing capabilities of sensors, computation of BCP(s, t) takes O((m2n2 + n4) log(mn + n2)) time and O(m2n2 +n4) space. For transparent obstacles, i.e., which only obstruct paths, but allows sensing, computation of BCP(s, t) takes O(nm2 + n3) time and O(m2 + n2) space. We believe, this is one of the first efforts to study the presence of obstacles in coverage problems in sensor networks.


 

Summer '10


Date: August 19, 2010
Presentor: Linna Wei
Paper Title: Joint Energy Management and Resource Allocation in Rechargeable Sensor Networks
Slides Link:
[PPT]

Abstract:
Energy harvesting sensor platforms have opened up a new dimension to the design of network protocols. In order to sustain the network operation, the energy consumption rate cannot be higher than the energy harvesting rate, otherwise, sensor nodes will eventually deplete their batteries. In contrast to traditional network resource allocation problems where the resources are static, time variations in recharging rate presents a new challenge. In this paper, we first explore the performance of an efficient dual decomposition and subgradient method based algorithm, called QuickFix, for computing the data sampling rate and routes. However, fluctuations in recharging can happen at a faster time-scale than the convergence time of the traditional approach. This leads to battery outage and overflow scenarios, that are both undesirable due to missed samples and lost energy harvesting opportunities respectively. To address such dynamics, a local algorithm, called SnapIt, is designed to adapt the sampling rate with the objective of maintaining the battery at a target level. Our evaluations using the TOSSIM simulator show that QuickFix and SnapIt working in tandem can track the instantaneous optimum network utility while maintaining the battery at a target level. When compared with IFRC, a backpressure-based approach, our solution improves the total data rate by 42% on the average while significantly improving the network utility.


Date: August 12, 2010
Presentor: Nam Nguyen
Paper Title: Community Structure in Large Complex Networks
Slides Link:
[PPT]

Abstract:
In this paper, we establish the definition of community fundamentally different from what was commonly accepted in previous studies, where communities were typically assumed to be densely connected internally but sparsely connected to the rest of the network. A community should be considered as a densely connected subset in which the probability of an edge between two randomly-picked vertices is higher than average. Moreover, a community should also be well connected to the remaining network, that is, the number of edges connecting a community to the rest of the graph should be significant.


Date: August 5, 2010
Presentor: Thang Dinh
Paper Title: Estimating multi-hop influence of nodes under Independent Cascade model

Abstract:
We analyze diffusion probabilities in networks under Independent Cascade Model in which each node once activated will activate its neighbors with some given probabilities. Since the problem is #P-complete, all we can hope for is an effective method to estimate the solutions via sampling method that is an fully polynomial randomized approximation scheme (FPRAS), a generally accepted as a robust notion of "approximation algorithm". Towards a FPRAS for the influence propagation problem, we present technical details of FPRAS for a closely related problem, namely network reliability.


Date: July 22, 2010
Presentor: Nam Nguyen
Paper Title: Detecting Highly Overlapping Community Structure by Greedy Clique Expansion
Slides Link:
[PPT]

Abstract:
In complex networks it is common for each node to belong to several communities, implying a highly overlapping community structure. Recent advances in benchmarking indicate that the existing community assignment algorithms that are capable of detecting overlapping communities perform well only when the extent of community overlap is kept to modest levels. To overcome this limitation, we introduce a new community assignment algorithm called Greedy Clique Expansion (GCE). The algorithm identifies distinct cliques as seeds and expands these seeds by greedily optimizing a local fitness function. We perform extensive benchmarks on synthetic data to demonstrate that GCE’s good performance is robust across diverse graph topologies. Significantly, GCE is the only algorithm to perform well on these synthetic graphs, in which every node belongs to multiple communities. Furthermore, when put to the task of identifying functional modules in protein interaction data, and college dorm assignments in Facebook friendship data, we find that GCE performs competitively.


Date: July 15, 2010
Presentor: Yilin Shen
Paper Title: Randomized Online Algorithms for Minimum Metric Bipartite Matching
Slides Link:
[PPT]

Abstract:
We present the  first poly-logarithmic competitive online algorithm for minimum metric bipartite matching. Via induction and a careful use of potential functions, we show that a simple randomized greedy algorithm is competitive on a hierarchically separated tree. Application of recent results on randomized embedding of metrics into trees yield the poly-logarithmic result for general metrics.


Date: July 8, 2010
Presentor:Dung Nguyen
Paper Title: Localized Algorithm for Precise Boundary Detection in 3D Wireless Networks
Slides Link:
[PDF]

Abstract:
This research focuses on distributed and localized algorithms for precise boundary detection in 3D wireless networks. Our objectives are in two folds. First, we aim to identify the nodes on the boundaries of a 3D network, which serve as a key attribute that characterizes the network, especially in such geographic exploration tasks as terrain and underwater reconnaissance. Second, we construct locally planarized 2-manifold surfaces for inner and outer boundaries, in order to enable available graph theory tools to be applied on 3D surfaces, such as embedding, localization, partition, and greedy routing among many others. To achieve the first objective, we propose a Unit Ball Fitting (UBF) algorithm that discovers a set of potential boundary nodes, followed by a refinement algorithm, named Isolated Fragment Filtering (IFF), which removes isolated nodes that are misinterpreted as boundary nodes by UBF. Based on the identified boundary nodes, we develop an algorithm that constructs a locally planarized triangular mesh surface for each 3D boundary. Our proposed scheme is localized, requiring information within one-hop neighborhood only. Our simulation results demonstrate that the proposed algorithms can effectively identify boundary nodes and surfaces, even under high measurement errors. As far as we know, this is the first work for discovering boundary nodes and constructing boundary surfaces in 3D wireless networks.


Date: June 17, 2010
Presentor: Linna Wei
Paper Title: Mobility Increases the Connectivity of K-hop Clustered Wireless Networks
Slides Link:
[PPT]

Abstract:
In this paper we investigate the connectivity for large-scale clustered wireless sensor and ad hoc networks. We study the effect of mobility on the critical transmission range for asymptotic connectivity in k-hop clustered networks, and compare to existing results on non-clustered stationary networks. By introducing k-hop clustering, any packet from a cluster member can reach a cluster head within k hops, and thus the transmission delay is bounded as theta(1) for any finite k. We first characterize the critical transmission range for connectivity in mobile k-hop clustered networks where all nodes move under either the random walk mobility model with non-trivial velocity or the i.i.d. mobility model. By the term non-trivial velocity, we mean that the velocity of nodes v is theta(1). We then compare with the critical transmission range for stationary k-hop clustered networks. We also study the transmission power versus delay trade-off and the average energy consumption per flow among different types of networks. We show that random walk mobility with non-trivial velocity increases connectivity in k-hop clustered networks, and thus significantly decreases the energy consumption and improves the power-delay trade-off. The decrease of energy consumption per flow is shown to be theta(logn/n^d) in clustered networks. These results provide insights on network design and fundamental guidelines on building a large-scale wireless network.


Date: June 10, 2010
Presentor: Thang Dinh
Paper Title: Separators in the Real World Practice
Slides Link:
[PPT]

Abstract:
Separators are vertices or edges in the graph that removal decompose the graph into separated components. Separators of small sizes have tremendous applications in VLSI network design, Load Balancing, Sparse Matrix Multiplication, .etc. We present and discuss on most effective approaches for edge/vertex separators.  The presentation will includes from the simple Kernighan-Lin Heuristic, Fiduccia-Mattheyses to more complicated Multilevel Partitioning and Multilevel Spectral Bisection based on eigenvector optimized via Rayleigh Quotient iteration.

 


Date: June 3, 2010
Presentor: Yilin Shen
Paper Title: Approximation Algorithms for Minimum-Cost k-Vertex Connected Subgraphs
Slides Link:
[PDF]

Abstract:
Authors present two new algorithms for the problem of finding a minimum-cost k-vertex connected spanning subgraph. The fi rst algorithm works on undirected graphs with at least 6k2 vertices and achieves an approximation factor of 6 times the kth harmonic number, which is O(log k). The second algorithm works on directed and undirected graphs. It gives an $O(\sqrt{n/epsilon})$-approximation algorithm for any $/epsilon > 0$ and $k  \le (1 - \epsilon)n$. The latter algorithm also extends to other problems in network design with vertex connectivity requirements. Authors' main tools are setpair relaxations, a theorem of Mader's (in the undirected case) and iterative rounding (general case).


Date: May 27, 2010
Presentor: Dung Nguyen
Paper Title: Approximating the Permanent
Slides Link:
[PPT]

Abstract:
A randomised approximation scheme for the permanent of a 0-1 matrix is presented. The task of estimating a permanent is reduced to that of almost uniformly generating perfect matchings in a graph; the latter is accomplished by simulating a Markov chain whose states are the matchings in the graph.
For a wide class of 0-1 matrices the approximation scheme is fully-polynomial, i.e., runs in time polynomial in the size of the matrix and a parameter that controls the accuracy of the output. This class includes all dense matrices (those that contain sufficiently many l’s) and almost all sparse matrices in some reasonable probabilistic model for 0-1 matrices of given density.

For the approach sketched above to be computationally efficient, the Markov chain must be rapidlyng: informally, it must converge in a short time to its stationary distribution. A major portion of the researcher is devoted to demonstrating that the matchings chain is rapidly mixing, apparently the first such result a Markov chain with genuinely complex structure. The techniques used seem to have general applicability, are applied again in the paper to validate a fully-polynomial randomised approximation scheme for partition function of an arbitrary monomer-dimer system.


Date: May 20, 2010
Presentor: Ying Xuan
Paper Title: Graph-Constrained Group Testing
Slides Link:
[PDF]

Abstract:
Non-adaptive group testing involves grouping arbitrary subsets of $n$ items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most $d$ defective items. Motivated by applications in network tomography, sensor networks and infection propagation we formulate group testing problems on graphs. Unlike conventional group testing problems each group here must conform to the constraints imposed by a graph. For instance, items can be associated with vertices and each pool is any set of nodes that must be path connected. In this paper we associate a test with a random walk. In this context conventional group testing corresponds to the special case of a complete graph on $n$ vertices. For interesting classes of graphs we arrive at a rather surprising result, namely, that the number of tests required to identify $d$ defective items is substantially similar to that required in conventional group testing problems, where no such constraints on pooling is imposed. Specifically, if T(n) corresponds to the mixing time of the graph $G$, we show that with $m=O(d^2 T^2(n) log(n/d))$ non-adaptive tests, one can identify the defective items. Consequently, for the Erdos-Renyi random graph $G(n,p)$, as well as expander graphs with constant spectral gap, it follows that $m=O(d^2 log^3(n))$ non-adaptive tests are sufficient to identify $d$ defective items. We next consider a specific scenario that arises in network tomography and show that $m=O(d^3 log^3(n))$ non-adaptive tests are sufficient to identify $d$ defective items. We also consider noisy counterparts of the graph constrained group testing problem and develop parallel results for these cases.


Date: May 13, 2010
Presentor: Linna Wei
Paper Title: Minimizing Energy Consumption with Probabilistic Distance Distributions in Wireless Sensor Networks
Slides Link:
[PPT]

Abstract:
Minimizing energy consumption in wireless sensor networks has been a challenging issue, and grid-based clustering and routing schemes have attracted a lot of attention due to their simplicity and feasibility. Thus how to determine the optimal grid size in order to minimize energy consumption and prolong network lifetime becomes an important problem. So far most existing work uses the average distances within a grid and between neighbor grids to calculate the average energy consumption, which we found largely underestimates the real value. In this paper, we propose, analyze and evaluate the energy consumption models in wireless sensor networks with probabilistic distance distributions. These models have been validated by numerical and simulation results, which shows that they can be used to optimize grid size and minimize energy consumption accurately. We also use these models to study variable-size grids, which can further improve the energy efficiency by balancing the relayed traffic in wireless sensor networks.


Date: May 06, 2010
Presentor: Nam Nguyen
Paper Title: Clustering Social Networks
Slides Link:
[PPT]

Abstract:
Social networks are ubiquitous. The discovery of close-knit clusters in these networks is of fundamental and practical interest. Existing clustering criteria are limited in that clusters typically do not overlap, all vertices are clustered and/or external sparsity is ignored. We introduce a new criterion that overcomes these limitations by combining internal density with external sparsity in a natural way. An algorithm is given for provably finding the clusters, provided there is a sufficiently large gap between internal density and external sparsity. Experiments on real social networks illustrate the effectiveness of the algorithm.


Date: May 03, 2010
Presentor: Thang Dinh
Paper Title: On Dense Subgraph Problems
Slides Link:
[PPT]

Finding dense subgraphs graphs such that  sum of weights of its edges is greater than sum of weights of its vertices arises in many CAD/CAM  applications and also in many geometric modeling contexts such as virtual reality, robotics, molecular modeling, teaching geometry, etc.

Dense graphs that present interest for finding a decomposition-recombination DR-plan are:

(a) minimum (smallest possible dense graphs),
(b) minimal (not containing any other dense subgraphs),
(c) maximum (largest dense ones),
(d) maximal (not contained in any other dense subgraph).

We present polynomial time algorithms for problems (b), (c) and (d). Problem (a) is shown to be NP-complete,
and various approximation algorithms are suggested, as well as explicit solutions for special cases.

Spring '10





Apr 22, 2010: "Community detection algorithms: A comparative analysis" PPT
Presented by:Ravi Tiwari

Abstract

Uncovering the community structure exhibited by real networks is a crucial step toward an understanding of complex systems that goes beyond the local organization of their constituents. Many algorithms have been proposed so far, but none of them has been subjected to strict tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of benchmark graphs, with heterogeneous distributions of degree and community size. The methods are also tested against the benchmark by Girvan and Newman Proc. Natl. Acad. Sci. U.S.A. 99, 7821 2002 and on random graphs. As a result of our analysis, three recent algorithms introduced by Rosvall and Bergstrom Proc. Natl. Acad. Sci. U.S.A. 104, 7327 2007 ; Proc. Natl. Acad. Sci. U.S.A. 105, 1118 2008 , Blondel et al. J. Stat. Mech.: Theory Exp. 2008 , P10008 , and Ronhovde and Nussinov Phys. Rev. E 80, 016109 2009 have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.



Apr 8, 2010: "Paired Approximation Problems and Incompatible Inapproximabilities" PDF
Presented by:Yilin Shen

Abstract

This paper considers pairs of optimization problems that are defined from a single input and for which it is desired to find a good approximation to either one of the problems. In many instances, it is possible to efficiently find an approximation of this type that is better than known inapproximability lower bounds for either of the two individual optimization problems forming the pair. In particular, we find either a $(1+\epsilon)$-approximation to $(1,2)$-TSP or a $1/\epsilon$-approximation to maximum independent set, from a given graph, in linear time. We show a similar paired approximation result for finding either a coloring or a long path. However, no such tradeoff exists in some other cases: for set cover and hitting set problems defined from a single set family, and for clique and independent set problems on the same graph, it is not possible to find an approximation when both problems are combined that is better than the best approximation for either problem on its own.



Apr 1, 2010: "An O(k3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design" PDF
Presented by:Dung T. Nguyen

Abstract

In the Survivable Network Design problem (SNDP), we are given an undirected graph G(V,E) with costs on edges, along with a connectivity requirement r(u, v) for each pair u, v of vertices. The goal is to find a minimum-cost subset E! of edges, that satisfies the given set of pairwise connectivity requirements. In the edge-connectivity version we need to ensure that there are r(u, v) edge-disjoint paths for every pair u, v of vertices, while in the vertex-connectivity version the paths are required to be vertex disjoint. The edge-connectivity version of SNDP is known to have a 2-approximation. However, no non-trivial approximation algorithm has been known so far for the vertex version of SNDP, except for special cases of the problem. We present an extremely simple algorithm to achieve an O(k3 log n)-approximation for this problem, where k denotes the maximum connectivity requirement, and n denotes the number of vertices. We also give a simple proof of the recently discovered O(k2 log n)-approximation result for the single-source version of vertex-connectivity SNDP. We note that in both cases, our analysis in fact yields slightly better guarantees in that the log n term in the approximation guarantee can be replaced with a log n term where n denotes the number of distinct vertices that participate in one or more pairs with a positive connectivityrequirement.







Mar 25, 2010: "Graph-theoretic QoS-aware Vulnerability Assessment for Network Topologies" PDF
Presented by:Ying Xuan

Abstract

How to assess the topology vulnerability of a network has attracted more and more attentions recently. With respect to multimedia network, which is a major network infrastructure, due to the rapid growing number of real-time multimedia applications developed, the discovery of topology weakness related to its quality of service (QoS) is of more interest. In this paper, we provide a novel graph-theoretic vulnerability assessment measurement for multimedia networks with multi-constraints for QoS. Specifically, we investigate the minimum set of nodes/links whose failure (removal) decreases the satisfactory level of the QoS-Optimal path between the source and destination nodes for multiple QoS constraints to a certain value, which is formed as graph optimization problem along with several exact and heuristic algorithms for different network cases. To our best knowledge, this is the first attempt to assess the network topology for its vulnerabilityw.r.t a quantified mixed metric for multiple QoS constraints.

Mar 18, 2010: "Latency-Bounded Minimum Influential Node Selection in Social Networks" PDF
Presented by:Incheol Shin

Abstract

As one of the essential problems in information diffusion process, how to select a set of influential nodes as the starting nodes has been studied by lots of researchers. All the existing solutions focus on how to
maximize the influence of the initially selected “influential nodes”, paying no attention on how the influential nodes selection could maximize the speed of the diffusion. In this paper, we consider the problem of influential nodes selection regarding to the propagation speed in social network information diffusion. We define a discrete optimization problem, called Fast Information Propagation Problem. We show that this problem is NP-hard problem when the time requirement for information propagation is exactly 1-hop. We also propose a Latency-bounded Minimum Influential Node Selection Algorithm to solve the problem in this case.

Mar 04, 2010: "EFFECT OF ATTACK ON SCALE-FREE NETWORKS DUE TO CASCADING FAILURE" PDF
Presented by:Nam Nguyen

Abstract

In this paper, based on the local preferential redistribution rule of the load after removing a node, we propose a cascading model and explore cascading failures on scale-free networks. Assuming that a failed node leads only to a redistribution of the load passing through it to its neighboring nodes, we study the response of scale-free networks subject to attacks on nodes. The network robustness against cascading failures is quantitatively measured by the critical threshold Tc, at which a phase transition occurs from normal state to collapse. For each case of attacks on nodes, four diferent attack strategies are used: removal by the descending order of the degree, attack by the ascending order of the degree, random removal of breakdown, and removal by the ascending order of the average degree of neighboring nodes of a broken node





Feb 25, 2010: "Lifetime and Coverage Guarantees Through Distributed Coordinate-Free Sensor Activation" PDF
Presented by:Linna Wei

Abstract

Wireless Sensor Networks are emerging as a key sensing technology, with diverse military and civilian applications. In these networks, a large number of sensors perform distributed sensing of a target field. Each sensor is a small battery-operated device that can sense events of interest in its sensing range and communicate with neighboring sensors. A sensor cover is a subset of the set of all sensors such that every point in the target field is in the interior of the sensing ranges of at least k different sensors in the subset, where k is a given positive integer. The lifetime of the network is the time from the point the network starts operation until the set of all sensors with non-zero remaining energy does not constitute a sensor cover. An important goal in sensor networks is to design a schedule, that is, a sequence of sensor covers to activate in every time slot, so as to maximize the lifetime of the network. In this paper, we design a polynomial-time, distributed algorithm for maximizing the lifetime of the network and prove that its lifetime is at most a factor O(logn*lognB) lower than the maximum possible lifetime, where n is the number of sensors and B is an upper bound on the initial energy of each sensor. Our algorithm does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in sensor networks. Each sensor only needs to know the distances between adjacent nodes in its transmission range and their sensing radii. In every slot, the algorithm first assigns a weight to each node that is exponential in the fraction of its initial energy that has been used up so far. Then, in a distributed manner, it finds a O(logn) approximation minimum weight sensor cover which it activates in the slot. Our simulations reveal that our algorithm substantially outperforms several existing lifetime maximization algorithms.







Feb 18, 2010: "Approximation schemes for wireless networks" PDF
Presented by:Thang N. Dinh

Abstract

Wireless networks are created by the communication links between a collection of radio transceivers. The nature of wireless transmissions does not lead to arbitrary undirected graphs but to structured graphs which we characterize by the polynomially bounded growth property. In contrast to many existing graph models for wireless networks, the property of polynomially bounded growth is defined independently of geometric data such as positional information.

On such wireless networks, we present an approach that can be used to create polynomial-time approximation schemes for several optimization problems called the local neighborhood-based scheme. We apply this approach to the problems of seeking maximum (weight) independent sets and minimum dominating sets. These are two important problems in the area of wireless communication networks and are also used in many applications ranging from clustering to routing strategies. However, the approach is presented in a general fashion since it can be applied to other problems as well.

The approach for the approximation schemes is robust in the sense that it accepts any undirected graph as input and either outputs a solution of desired quality or correctly asserts that the graph presented as input does not satisfy the structural assumption of a wireless network (an NP-hard problem).







Feb 4, 2010: "Approximation Algorithm for Data Broadcast in Wireless Networks" PDF
Presented by: Ravi Tiwari

Abstract

In my presentation I will be presenting the paper "Approximation Algorithm for Data Broadcast in Wireless Networks" by Rajiv Gandhi et. al. Following is the abstract of the paper:

Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it non-trivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete. We present a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem. We then consider the all-to-all broadcast problem where each node sends its own message to all other nodes. For the all-to-all broadcast problem, we present two algorithms with approximation ratios of 20 and 34, improving the best result available in the literature. Finally, we report experimental evaluation of our algorithms. Our studies indicate that our algorithms perform much better in practice than the worst-case guarantees provided in the theoretical analysis and achieve up to 37% performance improvement over existing schemes.






Jan 27, 2010: "On the Approximability of Influence in Social Networks" (SODA08) [PDF]
Presented by: Yilin Shin

Abstract

In this paper, the authors  study the spread of influence through a social network, in a model initially studied by Kempe, Kleinberg and Tardos [14, 15]: We are given a graph modeling a social network, where each node v has a (fixed) threshold tv, such that the node will adopt a new product if tv of its neighbors adopt it. Our goal is to find a small set S of nodes such that targeting the product to S would lead to adoption of the product by a large number of nodes in the graph. We show strong inapproximability results for several variants of this problem. Our main result says that the problem of minimizing the size of S, while ensuring that targeting S would influence the whole network into adopting the product, is hard to approximate within a polylogarithmic factor. This implies similar results if only a fixed fraction of the network is ensured to adopt the product. Further, the hardness of approximation result continues to hold when all nodes have majority thresholds, or have constant degree and threshold two. The latter answers a complexity question proposed in [10, 29]. We also give some positive results for more restricted cases, such as when the underlying graph is a tree.





Jan 14, 2010:  "Group Formation in Large Social Networks: Membership, Growth, and Evolution"[PPT]
Presented by: Dung T. Nguyen

Abstract

The processes by which communities come together, attract new members, and develop over time is a central research issue in the social sciences—political movements, professional  organizations, and religious denominations all provide fundamental examples of such communities. In the digital domain, on-line groups are becoming increasingly prominent due to the growth of community and social networking sites such asMySpace and LiveJournal. However, the challenge of collecting and analyzing large-scale timeresolved data on social groups and communities has left most basic questions about the evolution of such groups largely unresolved: what are the structural features that influence whether individuals will join communities, which communities will grow rapidly, and how do the overlaps among pairs of communities change over time? Here we address these questions using two large sources of data: friendship links and community membership on LiveJournal, and co-authorship and conference publications in DBLP. Both of these datasets provide explicit user-defined communities, where conferences serve as proxies for communities in DBLP. We study how the evolution of these communities relates to properties such as the structure of the underlying social networks. We find that the propensity of individuals to join communities, and of communities to grow rapidly, depends in subtle ways on the underlying network structure. For example, the tendency of an individual to join a community is influenced not just by the number of friends he or she has within the community, but also crucially by how those friends are connected to one another. We use decision-tree techniques to identify the most significant structural determinants of these properties. We also develop a novel methodology for measuring movement of individuals between communities, and show how such movements are closely aligned with changes in the topics of interest within the communities.






Jan 7, 2010: "Cost-effective Outbreak Detection in Networks"[PDF]
Presented by: Ying Xuan

Abstract

Which blogs should we read to avoid missing important information? Where should we place sensors in a water distribution network to quickly detect contaminants? These seemingly different problems share common structure: Outbreak detection can be modeled as a problem of selecting nodes (blogs, sensor locations, ...) in a network, in order to detect the spreading of a virus or information as quickly as possible. We present a general methodology for near optimal sensor placement in these and related problems. We demonstrate that many realistic outbreak detection objectives (e.g., detection likelihood, population affected) exhibit the property of “submodularity’’. We exploit submodularity to develop an efficient algorithm that scales to large problems, provably achieving near optimal placements, while being 700 times faster than a simple greedy algorithm. We evaluate our approach on several large real-world problems, including a model of a water distribution network, and real blog data. We also show how the approach leads to deeper insights in both applications, answering multicriteria trade-off, cost-sensitivity and generalization questions.




Fall '09






December 16, 2009: “Wormhole Attacks in Wireless Networks”
Presented by: Incheol Shin

Abstract

As mobile ad hoc network applications are deployed, security emerges as a central requirement. In this paper,
we introduce the wormhole attack, a severe attack in ad hoc networks that is particularly challenging to defend against. The wormhole attack is possible even if the attacker has not compromised any hosts, and even if all communication provides authenticity and confidentiality. In the wormhole attack, an attacker
records packets (or bits) at one location in the network, tunnels them (possibly selectively) to another location, and retransmits them there into the network. The wormhole attack can form a serious threat in wireless networks, especially against many ad hoc network routing protocols and location-based wireless
security systems. For example, most existing ad hoc network routing protocols, without some mechanism to defend against the wormhole attack, would be unable to find routes longer than one or two hops, severely disrupting communication. We present a general mechanism, called packet leashes, for detecting and thus
defending against wormhole attacks, and we present a specific protocol, called TIK, that implements leashes. We also discuss topology-based wormhole detection, and show that it is impossible for these approaches to detect some wormhole topologies.





December 2, 2009: “Sensor Relocation in Mobile Sensor Networks”
Presented by: Linna Wei

Abstract

Recently there has been a great deal of research on using mobility in sensor networks to assist in the initial deployment of nodes. Mobile sensors are useful in this environment because they can move to locations that meet sensing coverage requirements. This paper explores the motion capability to relocate sensors to deal with sensor failure or respond to new events. We define the problem of sensor relocation and propose a two-phase sensor relocation solution: redundant sensors are first identified and then relocated to the target location. We propose a Grid-Quorum solution to quickly locate the closest redundant sensor with
low message complexity, and propose to use cascaded movement to relocate the redundant sensor in a timely, efficient and balanced way. Simulation results verify that the proposed solution outperforms others in terms of relocation time, total energy consumption, and minimum remaining energy.





November 19, 2009: "Maximizing the Spread of Influence through a SocialNetwork"
Presented by: Thang Dinh

Abstract

Diffusion models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of “word of mouth” in the promotion of new products.  Using an analysis framework based on submodular functions, we show that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models; our framework suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks. We also provide computational experiments on large collaboration networks, showing that in addition to their provable guarantees, our approximation algorithms significantly out-perform nodeselection heuristics based on the well-studied notions of degree centrality and distance centrality from the field of social networks.







October 22, 2009:"AN APPROXIMATION ALGORITHM FOR THE MINIMUM-COST k-VERTEX CONNECTED SUBGRAPH*"

Presented by: Nam Nguyen

Abstract

We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k2. The approximation guarantee is six times the kth harmonic number (which is O(log k)), and this is alsoan upper bound on the integrality ratio for a standard linear programming relaxation.





October 15, 2009: “WORMEROS: A New Framework for Defending against Wormhole Attacks onWireless Ad Hoc Networks"
Presented by: Incheol Shin.

Abstract

Wormhole attack is a type of replay attack in wireless networks that has serious consequences and is hard to defend against. This is because the attacker does not need to modify packets or compromise wireless nodes. This paper introduces Wormeros, a new framework to detect wormhole attacks in wireless networks. The framework contains two phases namely suspicion and confirmation. Our solution does not require any special hardware (such as GPS) or expensive mechanisms (such as time synchronization) added to the wireless nodes. Using analysis and simulation, we show that our solution is effective in detecting
and defending against wormhole attacks.




October 8, 2009: “Jamming-resistant broadcast communication without shared keys"
Presented by:Ying Xuan.

Abstract

  Jamming-resistant broadcast communication is crucial for safety-critical applications such as emergency alert broadcasts or the dissemination of navigation signals in adversarial settings. These applications share the need for guaranteed authenticity and availability of messages which are broadcasted by base stations to a large and unknown number of (potentially untrusted) receivers. Common techniques to counter jamming attacks such as Direct-Sequence Spread Spectrum (DSSS) and Frequency Hopping are based on secrets that need to be shared between the sender and the receivers before the start of the communication. However, relying broadcast anti-jamming communication on either secret pairwise or group keys suffers from serious and sometimes even unsolvable scalability and key-setup problems or from weak jamming-resistance, respectively. In this work, we therefore propose a solution called Uncoordinated DSSS (UDSSS) that enables spread-spectrum anti-jamming broadcast communication without the requirement of shared secrets. It is applicable to broadcast scenarios in which receivers hold a certificate of the sender’s public key, but do not share a secret key with it. UDSSS can handle an unlimited amount of receivers while being secure against malicious receivers. We analyze the security and latency of UDSSS and complete our work by an
experimental evaluation on a prototype implementation.




October 1, 2009: Tracking Dynamic Boundary Fronts Using Range Sensors"
Presented by: Ravi Tiwari.

Abstract

The authors examine the problem of tracking dynamic boundaries occurring in natural phenomena using range sensors. Two main challenges of the boundary tracking problem are energy-efficient boundary estimations from noisy observations and continuous tracking of the boundary. The  authors propose a novel approach which uses a regression-based spatial estimation technique to determine discrete points on the boundary and estimates a confidence band around the entire boundary. In addition, a Kalman Filter-based temporal estimation technique is used to selectively refresh the estimated boundary to meet the accuracy requirements. Their algorithm for dynamic boundary tracking (DBTR) combines temporal estimation with an aperiodically updated spatial estimation and provides a low overhead solution to track boundaries without requiring prior knowledge  about the dynamics of the boundary. Experimental results demonstrate the effectiveness of our algorithm and estimated confidence bands achieve loss of coverage of less than 2 − 5% for a variety of boundaries with different spatial characteristics.





September 24, 2009: “Large Cliques in a power-law random graph"
Presented by: Dung T. Nguyen.

Abstract

We study the size of the largest clique !(G(n, )) in a random graph G(n, ) on n vertices which has power-law degree distribution with exponent . We show that for ‘flat’ degree sequences with > 2 whp the largest clique in G(n, ) is of a constant size, while for the heavy tail distribution, when 0 < < 2, !(G(n, )) grows as a power of n. Moreover, we show that a natural simple algorithm whp finds inG(n, ) a large clique of size (1 + o(1))!(G(n, )) in polynomial time.




September 10, 2009: “Distributive Boundary estimation Using Sensor Network"
Presented by: Ravi Tiwari.

Abstract

The authors examined the problem of determining boundaries occurring in natural phenomena using sensornetworks. Sensor nodes remotely collect data about various points on the boundary. From this data, we estimate the boundary along with the confidence intervals using a regression relationship among sensor locations and the distances to the boundary. The confidence intervals are guaranteed to be narrower than a specified maximum width. Our distributed boundary estimation strategy uses a hierarchical structure of clusters of sensor nodes and requires 20−50% less messages as compared to a centralized scheme. The computed intervals show desired coverage of the true boundary points. Further, motivated by the practical need to estimate the boundary with a minimum number of sensors, we develop an adaptive approach for turning sensors on and off. The number of ON sensors in this scheme is only about 15% more than what a Practical Oracle needs, to evaluate the boundary and confidence intervals around it. Our algorithms are also evaluated using data from real sensors on a testbed.




September 3, 2009: “Constant-Factor Approximation Algorithms for Identifying Dynamic Communities"
Presented by: Nam Nguyen.

Abstract

We propose two approximation algorithms for identifying communities in dynamic social networks. Communities are intuitively characterized as “unusually densely knit” subsets of a social network. This notion becomes more problematic if the social interactions change over time. We show that the algorithms are small constant factors approximation of the optimums, regardless of the input size. They are the first algorithms for inferring communities in dynamic networks with provable approximation guarantees.




August 27, 2009: “What Cannot be Computed Locally?"
Presented by : Thang N. Dinh

Abstract

We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors  O(n^(c/k^2)/k) for some c > 1/4 or O(d^(c/d^2)/d) where d is maximum degree.
In other words the number of rounds required in order to achieve a constant or even only a polylogarith-
mic approximation ratio is at least  O(sqrt( log n/ log log n)) and O(sqrt( log d/ log log d)).


Summer '09






August 20, 2009: “Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information”
Presented by : Incheol Shin

Abstract

In the talk the paper "Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information" will be presented in which the author proposed a novel algorithm for detecting wormhole attacks in wireless multi-hop networks. The algorithm uses only connectivity information to look for forbidden substructures in the connectivity graph. The proposed approach is completely localized and, unlike many techniques proposed in literature, does not use any special hardware artifact or location information, making the technique universally applicable. The algorithm is independent of wireless communication models. However, knowledge of the model and node distribution helps estimate a parameter used in the algorithm. Further the author presented simulation results for three different communication models and two different node distributions, and show that the algorithm is able to detect wormhole attacks with a 100% detection and 0% false alarm probabilities whenever the network is connected with high probability. Even for very low density networks where chances of disconnection is very high, the detection probability remains very high.





August 13, 2009: “Randomized Rounding for Solving Critical Node Detection Problem”
Presented by : Ying Xuan

Abstract

Critical Vertex/Edge Detection has been shown to be a promising but tough problem due to the difficulties in optimizing the global pairwise connectivity. Fortunately, plenty of advanced mathematical techniques have been proposed to solve this problem, but a majority of them can only provide pseudo-approximation algorithms. To this end, we investigated an Integer Program (IP) formulation of the Critical Node(Vertex) Detection problem and aimed to obtain a true approximation algorithm with O(k\log n) ratio, using a randomized rounding scheme. However, some problems emeried as obstacles to complete the solution. Therefore, I would like to show our basic idea and discuss on the problems to overcome. Hopefully we could come up with helpful ideas to make it through.

August 6, 2009: “Approximating the k-Multicut Problem”
Presented by : Yilin Shen

Abstract

In the talk the paper "Approximating the k-Multicut Problem" is presented in which the author studied the k-multicut problem: Given an edgeweighted undirected graph, a set of l pairs of vertices, and a target k ≤ l, find the minimum cost set of edges whose removal disconnects at least k pairs. This generalizes the well known multicut problem, where k = l. We show that the k-multicut problem on trees can be approximated within a factor of $\frac{8}{3}+\epsilon$, for any fix $\epsilon > 0$, and within $O(log^{2}nloglog n)$ on general graphs, where n is the number of vertices in the graph.For any fixed $\epsilon> 0$, we also obtain a polynomial time algorithm for k-multicut on trees which returns a solution of cost at most $(2 + \epsilon).OPT$, that separates at least $(1−\epsilon)·k$ pairs, where OPT is the cost of the optimal solution separating k pairs. The proposed techniques also give a simple 2-approximation algorithm for the multicut problem on trees using total unimodularity, matching the best known algorithm [8].





July 8, 2009: “Primal Dual Approximation Algorithms for Directed Generalized Steiner Networks”
Presented by : Nam Nguyen

Abstract

In this talk, I will introduce and talk about a solution for the Directed Steiner Forest problem, making use of the Primal Dual method and some special subsets (Violated subsets) of a graph. Basically, we begin with the initial solution consisting of sets of sources and shrinks and built up the solution for IP and LP simultaneously. The experimental results for this solution will also be introduced.



July 1, 2009: “Coverage of Phenomena Cloud Using Wireless Sensor Network”
Presented by : Ravi Tiwari

Abstract

A phenomenon that expands, shrinks, and changes its location in the contiguous space with the respect to time is called a phenomena cloud. For instance: forest fire, Mud Flow, Bio-chemical material diffusion, Oil spills. In the presentation I discuss the solution to the phenomena cloud problem formulated as follows:  Given a set of sensors forming a Wireless Sensor Network (WSN), represented by a graph G=(V,E). Consider a phenomena cloud occurring within the space covered by the WSN G, the problem is to cover the phenomena cloud minimizing the network resources used and maximizing the sensor network lifetime.




June 24, 2009: “Geometric Embeddings of Metric Spaces”
Presented by : Thang Dinh

Abstract

A geometric network is a graph mapped into the Euclidean plane. It is said to be a geometric spanner if the network distance between any pair of nodes is bounded by a constant times their Euclidean distance. One is interested in spanners with other useful properties such as few edges, small weight, small node degree, or small link diameter. Geometric networks and spanners play an important role in telecommunication, motion planning (robotics), pattern matching, data compression, gene analysis, and sensor networks. Apart from these applications, geometric spanners have had great impact on the construction of approximation algorithms, e.g., for the traveling salesman problem.




June 3, 2009: “Jamming Attack Detection and Countermeasures In Wireless Sensor Network Using Ant System”
Presented by : Incheol Shin

Abstract

Sensors have varied constraints, which makes the network challenging for communicating with its peers. In this paper, an extension to the security of physical layer of a predictive sensor network model using the ant system is proposed. The Denial of Service (DoS) attack on sensor networks not only diminishes the network performance but also affects the reliability of the information making detection of a DoS threat is more crucial than ecovering from the attack. Hence, in this paper, a novel approach in detecting the DoS attack is introduced and analyzed for a variety of scenarios. The DoS attack is dependent on the vulnerabilities in each layer, with the physical layer being the lowest layer and the first to be attacked by jammers. In this paper, the physical layer DoS attack is analyzed and a defense mechanism is proposed. Classification of the jammer under various attack scenarios is formulated to predict the genunity of the DoS attacks on the sensor nodes using receiver operating characteristics (ROC). This novel approach helps in achieving maximum reliability on DoS claims improving the Quality of Service (QoS) of WSN.


May 27, 2009: “Euclidean Squared Metric based SDP for graph partitioning problems” (Contd)
Presented by : Ying Xuan




May 21, 2009: “Euclidean Squared Metric based SDP for graph partitioning problems”
Presented by : Ying Xuan

Abstract

Euclidean Squared Metric Assignment has been widely adopted and combined with Semi-Definite Programming for various graph partitioning problems, for example minimum bisection, sparsest cut, k-partitioning. Thanks to existing fruitful geometric embedding results(distortion), a underlying $\sqrt{\log n}$ approximation algorithm has been obtained toward this problem family. In this talk, I would like to briefly go through two papers: ARV '04(Geometric Embeddings, Graph Partitioning, and Expander flows) and SODA' 09 (Partitioning graphs into balanced components). For the first one, I would use its online slides, which include fundamental concepts about the SDP formulation based on l_2^2 assignment and randomized projection rounding. You could refer to it via this website: www.cs.princeton.edu/~arora/talks/geomexpansion.ppt. For the second one, I am writing it and would send all of you the slides by tomorrow noon, which will include a spreading metric-based algorithm and corresponding analysis.


Spring '09

April 16, 2009: “Spreading Matrix”
Presented by : Thang Dinh


April 09, 2009: “Distributed identification of trigger nodes against reactive jamming attacks
Presented by : Incheol Shin

Abstract

There exist many studies against reactive jamming attacks, however, these methods, i.e. frequency hopping or channel surfing, require excessive computational capabilities on wireless devices which are serious side effects in wireless sensor networks. To avoid the problems in existing methods, we propose a novel approach against reactive jamming attacks by identifying the trigger nodes, whose transmissions activate any reactive jammers. The identification of these trigger nodes can help us (i) carefully design a better routing protocol by switching these nodes into only receivers to avoid activating jammers and (ii) locate the jammers based on the trigger nodes, thus providing an alternative mechanism against reactivejamming attacks.In the presentation I will talk distributed version of identification of trigger node against jamming attack.


Mar 26, 2009:On approximation algorithms for Interference-Aware Broadcast Scheduling in 3D Wireless Sensor Networks

Presented by : Ravi Tiwari


Mar 5, 2009: “Distributed identification of trigger nodes against reactive jamming attacks
Presented by : Incheol Shin

Abstract

There exist many studies against reactive jamming attacks, however, these methods, i.e. frequency hopping or channel surfing, require excessive computational capabilities on wireless devices which are serious side effects in wireless sensor networks. To avoid the problems in existing methods, we propose a novel approach against reactive jamming attacks by identifying the trigger nodes, whose transmissions activate any reactive jammers. The identification of these trigger nodes can help us (i) carefully design a better routing protocol by switching these nodes into only receivers to avoid activating jammers and (ii) locate the jammers based on the trigger nodes, thus providing an alternative mechanism against reactivejamming attacks.In the presentation I will talk distributed version of identification of trigger node against jamming attack. 


 

Feb 26, 2009: “A General Approach for Modules Identification in Evolving Networks”
Presented by : Thang Dinh

Abstract

Most complex networks exhibit a network modular property, that is nodes within a network module are more densely connected among each other than with the rest of the network. Knowing the behavior of modules with respect to the movements of vertices and edges in evolving networks can directly help predict interdependent responses of network components. It also helps to design a robust system with the minimum costs. A large number of algorithms have been developed to identify modules in networks. However, most of them are not designed for large and highly dynamic networks in which the structure adjusts accordingly. We introduce a general approach to efficiently detect and trace evolving of modules in a dynamic network. Through analyzing features of the optimal partition of network into modules, we propose a compact representation of the network. Then, the compact representation conveying the network structure is usedto guide the identifying of modules in next step.


Feb 19, 2009: "Network Reliability"
Presented by: Ying Xuan

Abstract

Considering that the our current topics of probabilistic routing, community structure and critical node detection in evolving graph, may have some relationships with the network reliability, I would like to talk about some fundamental concepts and exact algorithms for the network reliability computation.


 Jan 29, 2009: "On Critical Node Detection In Static Networks"
Presented by:
Ying Xuan

Abstract

The critical node detection problem has shown huge interests for researchers in both bio-infomatics and social networks. Due to the dynamic topology in these environments, few efficient solutions with low computational overhead have been proposed. Even for the same problem in static networks, only several centralized heuristics are presented. In this presentation, we would study on several potential methods for detecting critical nodes in static context, including making benefit from p-Section problem by semidefinite programming, relaxing and rounding IP program and possibly de-touring to dual problem. Moreover, two centralized heuristics would be given for sparse networks, meanwhile preliminary simulation results will be shown. Considering the recent papers we read on non-unique probe detection using group testing, as well as converting d-disjunct matrix to graph element problem, we may further discuss on the possibility of applying group testing or superimposed codes to this problem.



Jan 22, 2009: "Tilling and coloring  2D plane and 3D space" 
Presented by:
Ravi Tiwari

Abstract

The presentation is about a technique to perform tilling and  coloring of 2D plane using regular hexagons in such a way that no two regular hexagons  at a distance less than $d\in R^+$ can have same color. Further this technique is extended for tilling and coloring the 3D-space. In this case the 3D space is tilled using truncated octahedrons. Furthermore the  truncated octahedrons tiling the 3D space are colored such that two truncated octahedron with same colors are at least distance $d\in R^+$ apart.




Fall '08

November 6, 2008: “Detecting Critical Nodes in Probabilistic Graph”
Presented by: 
Ying Xuan


Abstract

A brief description of this problem can be: Given a connected probabilistic graph where each edge has an independent probability to fail, find out no more than k critical nodes, whose removal will result in maximum graph fragment, i.e., minimum pairwise connectivity.


October  23, 2008: “Non-adaptive fault diagnosis for all-optical networks via CGT on graph”
Presented by: Yilin Shen

Abstract

In the paper “Non‐Adaptive Fault Diagnosis for All‐Optical Networks via Combinatorial Group Testing on Graphs”, a new technique framework, combinatorial group testing on graphs, was defined and it has been used in probing the fault diagnosis of optical networks with some specific topology or  properties. Consider the blocking attack in wireless sensor networks, our objective is to detect all malicious nodes by using the below new technique framework. Based on the protocol “Secure Implicit Sampling”, we can find all victim nodes out. Then based on these victim nodes and broadcast tree, a part of malicious nodes can be detected and some of good nodes can be identified as well. By constructing a group of sequential broadcast trees, we can finally detect all malicious nodes.


 
October  16, 2008
"Minimum Latency Broadcast Scheduling in Wireless Ad hoc Network modeled as a Disk Graph"
Presented by: Ravi Tiwari

Abstract

The presentation focuses on various approaches for solving the Minimum Latency Broadcast Scheduling problem in Wireless Ad hoc Network  where the nodes have different transmission ranges. Two approaches along with their approximation ratios were discussed. 


October  16, 2008: "Practical results and the issues of DoS detection using Group Testing"
Presented by: Incheol Shin



September 25, 2008
: "Community Network Detection in Network"
Presented by: Thang Dinh


 
September 18, 2008
: "DoS attack detection using Group Testing"
Presented by: Ying Xuan

Abstract

Numerous detection methods for DoS attacks have been proposed and developed, however, most of them suffer the long detection delay and high false positive/negative rate; especially in the application layer DoS attacks. We propose a novel approach for identifying this  attack type based on the group testing (GT) technique which helps to overcome the limitations of current detection approaches. Based on a new size constraint group testing mode and 2-mode detection framework, we are able to efficiently tackle application-layer attacks by three detection algorithms. Without requirement for the acknowledge of the client distribution, group testing techniques are applicable for more general defense topics.



September 11, 2008
: "Integer Program Formulation for Broadcast Scheduling Problem in Wireless Network"
Presented by: Ravi Tiwari

Abstract

Given an undirected disk graph G = (V;E), and a designated node s in V known as the source. The source node s is initially having an information which is required to be broadcasted to all the other nodes v in (V\ s) in the network. The problem  is to generate a Conflict and Interference aware broadcast schedule for propagating the information starting from the source node to all the other nodes in the network in minimum latency time. In the presentation an Integer program formulation of the above problem was discussed.  


September 4, 2008: "O(1) Time Complexity Look-Up Service in P2P"
Presented by: Incheol Shin





Spring '08



May 6, 2008: "Detection of Denial of Message attack in wireless sensor networks based on group testing"
Presented by: Incheol Shin (Continued the last week talk)



April 29, 2008: "Detection of attacks in wireless sensor networks based on group testing"
Presented by: Incheol Shin


Abstract

Wireless sensor networks security has been getting important as those have been used in several fields. Since the nature of the dynamic behavior in the sensor networks, these networks are very vulnerable from the attackers. Existing researches shows some of efficient way to detect the replication attacks but most of them are not suitable for wireless sensor because of the unique constraints such as low battery life, ad-hoc communications. We will discuss about the how the attacks work in the sensor networks and approaches to this attack based on group testing technique.


April 22, 2008: "Concepts and Constructions of d-disjunct matrix"
Presented by: Ying Xuan

Abstract

With prompt identification ability and low decoding overhead, disjunct matrix has been proposed and promoted as a novel stipulation method for group testing. Although the earliest research on this topic could date back to 1964, there are still plenty of open questions and thus contain great potentials for mining. To nourish your possible interest on group testing, we would study together some details of the motivation, definition and construction for this disjunct matrix, followed by corresponding performance analysis.


April 15, 2008: "Testing k-connectivity and finding disjoint paths in a Graph (Directed and Undirected)"
Presented by: Ravi Tiwari (Continued the previous talk)



April 8, 2008: "Minimum energy anycast routing in dynamically evolving networks"
Presented by: Vishak Srinivasan

Abstract

Here we will be discussing about the anycast routing in dynamically evolving networks. Previously, we saw some of the dynamic and evolving models. Setting up a graph model for anycast routing and defining their properties, which builds anycast trees such that energy consumed by the network model is minimized. Also, we need to show that computing these anycast trees under such circumstances is NP-Complete. Finally propose a heuristic and an approximation algorithm to solve the problem.


April 1, 2008: "Testing k-connectivity and finding disjoint paths in a Graph (Directed and Undirected)"
Presented by: Ravi Tiwari



March 25, 2008: "Broadcast scheduling in wireless networks - Simulation Results"
Presented by: Reza Mahjourian

Abstract

Discussing the simulation results from the recently submitted work.



March 18, 2008: "Interference-aware Channel Assignment based on Superimposed Codes in MR-MC wireless mesh networks"
Presented by: Ying Xuan

Abstract

As the theoretical foundation of Group Testing (GT), Superimposed Codes (SC) has been thoroughly studied and applied into various classic areas, such as multi-access communications, pattern matching, cryptography and circuit complexity. Nowadays, besides malice detection that we are studying on, several new applications have been proposed, one of which is the "interference-aware channel assignment (CA) in general wireless mesh networks". In this talk, we will study together over the basic strategies and two localized algorithms for this CA problem, which contains large potential as a fresh topic. Meanwhile, solutions within this work might enlighten our future research on other related issues.


March 4, 2008: "Resource Monitoring for the Detection of Attacks."
Presented by: Incheol Shin

Abstract

There have been intensive researches on detection and defense against DDoS as it is becoming a serious devastating attacks on internet, and various types defenses has came from the researches. The methods of defenses against any type of DDoS or DoS should differ from each other based on which types of attacks they use and should evolve to protect the systems from more virulent attacks as the they evolve to be mightier attackers. However, the detection method can be approached from the view point of system resources because the overall goal of these types of attacks is to make system resources unavailable to legitimate users. This gives us an idea for designing a system framework for detection of cyber attacks to provide common framework for the detections. We will discuss more about how to perform a detection based on monitoring system resources and what the advantages for those detection mechanisms are and flaws of existing detection mechanisms.



February 26, 2008: Broadcast scheduling in wireless networks
Presented by: Reza Mahjourian

Abstract

We present a brief review of the three broadcast algorithms discussed in our recent paper and we present our recent simulation results. We try to justify the simulation results and explain where each algorithms is performing better or worse than the other algorithms.



February 19, 2008: "A Real-time perspective on the Mobility Models in Self-organizing Ad Hoc Networks"  
Presented by Vishak Srinivasan (Continued the last presentation)

Abstract

With the advent of new communication networks, Self Organizing Networks aka Mobile Ad hoc Networks, it's important to study the dynamic behavior of such networks. Underlying mobility of users, varying link congestion, node and link faults etc. all needed to be analyzed to a great extent. This brings us to the need for designing a dynamically evolving mobility model where we can study and improve the performance of these dynamically changing ad hoc networks. Basically, we will be discussing in detail regarding the works so far on these dynamic network models, their algorithmic techniques and their design evolutions.



February 12, 2008: "A Real-time perspective on the Mobility Models in Self-organizing Ad Hoc Networks"
Presented by: Vishak Srinivasan

Abstract

With the advent of new communication networks, Self Organizing Networks aka Mobile Ad hoc Networks, it's important to study the dynamic behavior of such networks. Underlying mobility of users, varying link congestion, node and link faults etc. all needed to be analyzed to a great extent. This brings us to the need for designing a dynamically evolving mobility model where we can study and improve the performance of these dynamically changing ad hoc networks. Basically, we will be discussing in detail regarding the works so far on these dynamic network models, their algorithmic techniques and their design evolutions.



February 5, 2008: "Information and defenses against Denial of Service (DoS), Distributed Denial of Service (DDoS) attacks"
Presented by: Incheol Shin

Abstract

There have been intensive researches on detection and defense against DDoS as it is becoming a serious devastating attacks on internet, and various types defenses has came from the researches. In order to protect networks against the DDoS attacks, it is desirable to clarify the vulnerabilities of the networks from the attacker's view point. From this survey of various kinds of attacks and defenses against them, we can point out the existing problem and limitation for the better solution.



January 29, 2008: "The Quality of Connected Dominating Sets in Wireless Network"
Presented by: Ning Zhang

Abstract

We consider the problem of generating connected dominating sets (CDS) for applications in wireless network. Existing algorithms for solving this problem consider number of nodes in the CDS as the single criteria. We report algorithms for generating CDS by considering diameter and interference as the additional factors. Analysis shows that the proposed algorithms can generate diameter reduced and interference aware dominating sets without increasing the size of the solution.



January 22, 2008: "Fault Tolerant Virtual Backbone for Wireless Ad hoc Network with Uni-directional links"
Presented by: Ravi Tiwari


January 15, 2008: "On Detection of Malicious Users Using Group Testing techniques"
Presented by: Ying Xuan

Abstract 

Malicious users are a great security threat currently in the networking area. Detecting all these malicious users in the timely fashion becomes very important, yet no work in literature has addressed this issue. Motivated by this detection problem, we introduce a new group testing model, called Size Constraint Group Testing (SCGT). Based on this model, we proposed several algorithms, both sequential and non-adaptive for various networking scenarios. Theoretical analysis shows that these algorithms can detect all malicious users in a short amount of time. We also provide several fundamental results on SCGT, revealing some necessary constraints to obtain an O(1) time complexity algorithm. In the future, we would focus on false-tolerant algorithm and integrating with IP traceback to locate the malicious users.



Fall '07

December 4, 2007: "Multi-Anycast Session with Minimum energy consumption in Wireless Sensor Networks"
Presented by: Vishak Srinivasan



November 20, 2007: "Interference-free Minimum-Latency Broadcast Scheduling in Wireless Networks" (Continued the last week's talk)
Presented by: Reza Mahjourian




November 13, 2007: "Interference-free Minimum-Latency Broadcast Scheduling in Wireless Networks"
Presented by: Reza Mahjourian



October 23, 2007: "Efficient Way to Connect Dominating Tree with Minimum Weight"
Presented by: Incheol Shin




October 9, 2007: "Virutal IP Attack Trace with Combinatorial Group Testing"
Presented by: Ying Xuan  


October 2, 2007: "Weighted Connected Dominating Set Problem"
Presented by: Bo Li



September 18, 2007: "Fault Tolerant Virtual Backbone for a wireless ad hoc network with bi-directional links"
Presented by: Ravi Tiwari



September 11, 2007: "Connected dominating sets with bounded diameter"
Presented by: Ning Zhang



August 7, 2007: "Min-cost Multicost of Selfish Information Flows"
Presented by: Bo Li



July 23, 2007: "Connected Dominating Sets with bounded diameter"
Presented by: Ning Zhang



June 18, 2007: "A linear programming perspective of DT"
Presented by: Bo Li



May 29, 2007: "A constant approximation algorithm for interference aware broadcast in  Wireless networks"
Presented by: Incheol Shin


April 26, 2007: "Energy-efficient broadcast tree in wireless network"
Presented by: Ning Zhang



April 12, 2007: "Maximum throughput and fair bandwidth allocation in multichannel wireless mesh network"
Presented by: Ravi Tiwari



April 5, 2007: "Wireless Mesh Networks"
Presented by: Ravi Tiwari



March 29, 2007: "Routing, Anycast, and Multicast for Mesh and Sensor Networks" (Continued previous presentation) 
Presented by: Bo Li 



March 22, 2007: "Routing, Anycast, and Multicast for Mesh and Sensor Networks"
Presented by: Bo Li



February 22, 2007: "Fault Tolerant CDS"
Presented by: Ning Zhang



February 15, 2007: "Redundancy and Coverage Detection in Sensor Networks"
Presented by: Tania  Mishra




February 1, 2007: "Set cover"
Presented by: Ravi Tiwari




January 25, 2007: "Dynamic CDS"
Presented by: Bo Li



Summer '07





 

August 7, 2007: Min-cost Multicost of Selfish Information Flows
Presented by Bo Li


July 23, 2007: Connected Dominating Sets with bounded diameter
Presented by Ning Zhang


June 18, 2007: A linear programming perspective of DT
Presented by Bo Li


May 29, 2007: A constant approximation algorithm for interference aware broadcast in  Wireless networks
Presented by Incheol Shin



Spring '07



April 26, 2007: Energy-efficient broadcast tree in wireless network
Presented by Ning Zhang


April 12, 2007: Maximum throughput and fair bandwidth allocation in multichannel wireless mesh network
Presented by Ravi


April 5, 2007: Wireless Mesh Networks
Presented by Ravi


March 29, 2007: Routing, Anycast, and Multicast for Mesh and Sensor Networks 2
Presented by Bo Li


March 22, 2007: Routing, Anycast, and Multicast for Mesh and Sensor Networks 1
Presented by Bo Li


February 22, 2007: Fault Tolerant CDS
Presented by Ning Zhang


February 15, 2007: Redundancy and Coverage Detection in Sensor Networks
Presented by Mishra


February 1, 2007: Set cover
Presented by Ravi


January 25, 2007: Dynamic CDS
Presented by Bo Li