SEMINAR TALK ARCHIVE
Spring '11 |Fall '10 |Summer '10 |Spring '10 | Fall '09 | Summer '09 | Spring '09 | Fall '08 | Spring '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
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
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
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
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
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
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
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”
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”
Abstract
Feb 26, 2009: “A General Approach for Modules Identification in Evolving Networks”
Presented by : Thang Dinh
Abstract
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.
Presented by: Ying Xuan
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.
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.
October 16, 2008 "Minimum Latency Broadcast Scheduling in Wireless Ad hoc Network modeled as a Disk Graph"
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.
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"
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.
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.
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
|
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
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