A. Optimal Use of Social Networks for Fast Information Spread & Counter-messaging

Social network applications on Facebook, MySpace, Bebo, etc. are excellent examples of viral marketing. The spreading of an application starts with one user installing the application, then the application sends ‘Invitations’ to all friends of the user. Furthermore, for every activity of the application the application will notify friends with a mini-story or feed. In turn, friends of the users get curious about the application, install it and continue the exponentially viral growing process. The more initial users selected, the faster the application will spread through the network. However, due to limits on resources companies often want to target a small group of the most influential users so that after a chain-reaction of influence the company can reach to users in the whole network or a segment of the network.

Objectives:

• Provide models and solutions for time-constrained viral marketing in online social networks
• Study the security aspects of online social networks, including misinformation countermeasures and sharing sensitive information without exposing to unintended audience

B. Adaptive Approximation Algorithm for Community Structure Detection

Community structure is defined as a subgraph such that there is a higher density of edges within the subgraph than between them. This has applications in many domains, not only in computer networks, but also in computational biology, social research, life sciences and physics.  We focuses on complex, dynamic, and evolving over time, yet often greatly affected by uncertain factors, which may arise in many forms, including natural or man-made interferences. 

Objectives:

• Develop mathematical models and efficient approximation algorithms to determine the community structure of a given network;
• Handle the dynamic and evolution of community structures; provide a mathematical framework for several existing problems in dynamic networks such as routing protocols in DTN and MANETs, network design and management.

C. Fast Detecting Disjoint and Overlapping Community Structures

Many problems in reality take the forms of complex networks and their underlying organization exhibit the property of containing communities, i.e. groups of tightly internally-connected and sparsely externally-connected nodes in the network structure. Community detection is the problem of identifying those communities in a given network with or without extra information such as the number of communities, and with overlapping or non-overlapping communities.

Applications:

• Community detection methods are of great advantages in social-aware routing in MANETs and worm containment on social networks.

A. Information Leakage in Online Social Networks

As an imperative channel for rapid information propagation, OSNs also have their disruptive effects. One of them is the leakage of information, i.e., information could be spread via OSNs to the users whom we may not willing to share with. Thus the problem of constructing a circle of trust to share the information with as many friends as possible without further spreading it to unwanted users has become a challenging research topic recently. Our work is the first attempt to study the Maximum Circle of Trust problem which seek  for a close set of friends such that the chance for information spread out to the unwanted users is the smallest. We propose a Fully Polynomial-Time Approximation Scheme (FPTAS)  

Objectives:

• Develop and justify leakage models in online social networks
• Devise scalable and efficient methods to construct  circles of trust for smart sharing on the fly, given the unwanted targets.

A. Sybil attack and limiting the spread of misinformation

Sybil attack and misinformation spreading are two crucial problems that recently occur in communication networks, especially in OSNs. In sybil attack, sybil nodes with multiple fake identities are trying to attain and then influence the others as if they are honest ones, as in
recommendation systems or online votes. In the other issue, the spread out of misinformation in a social network can lead to an undesired reaction in the wide public. These two problems are very challenging due to the huge network scale and the unprediction of social influence.

Objectives:

• Effective algorithms for detecting sybil nodes
• Selecting the smallest set of nodes to counter misinformation propagation with good approximation guarantees.

A. Complex Network Vulnerability Assessment

Communication networks play a vital role in the day-to-day routine of all sectors of our society. Unfortunately, these systems are often greatly affected by several uncertain factors, including external natural or man-made interferences (e.g., severe weather and enemy/malicious attacks.) The failure of a few key nodes that play a vital role in maintaining the network’s connectivity can break down its operation.

Objectives:

• Finding the set of disruptors who play a key role in maintaining the network connectivity, thus it can serve as a fundamental framework for the design of network topology, network vulnerability and reliability.
• Investigate what role the power-law distribution plays in the complexity and approximation of solutions.

B. Vulnerability of Power Law Networks

In 1999, it is discovered that almost real large-scale networks follow the same type of graphs called power law graphs. In these realistic networks, the degree distribution follows the power law distribution, at least asymptotically.  The fraction of nodes with degree k is proportional to the reciprocal of k power C where C is a constant named the exponential factor. The emergence of the power law distribution has changed the existing approaches to several optimization problems on networks. Institutively we can get faster algorithms solving a particular problem if we exploit all the properties of the problem as well as the type of networks. However, using the power law distribution in designing new algorithms is challenging and it requires new techniques and approaches. In other direction is to reevaluate the difficulty of the problem in this type of networks. Many problems are proved hard to be solved on general graphs but they may be easier to solve on power law graphs.
Objectives::

C. Group Testing and its Applications to defending Denial-of-Service Attacks

Group Testing, also known as Pooling Design, is a technique to speed up the detection of affected blood samples within a large sample population in Biology. However, it has rarely been used for network security problems due to the limitations in its conventional models and algorithms. Investigating its advantage for defending the Denial-of-Service (DoS) attacks at different network layers can lead to a series of anti-DoS solutions with theoretical and experimental performance guarantee.

Objectives:

A. Wireless Network Coverage and Power Assignment

In wireless sensor networks, maintenance the network coverage is one of the most important tasks to guarantee the quality of monitoring results. There are many factors that affect the coverage of wireless sensor networks. In the deploying phase, the full coverage may not be achieved because of random deployment. Then in the operation phase, some sensors may stop working due to the energy depletion or malfunctions. If we have redundant mobile sensor in the monitored area, we can schedule them to necessary locations that set up the coverage. The scheduling algorithm should be fast and light because the resource of sensors is very limited.

Objectives:Objectives:Objectives:

B. Broadcast Scheduling in Wireless Ad hoc Networks

Broadcast has been a fundamental mechanism to lower down delivery time latency in wireless ad hoc networks. The intrinsic broadcasting nature of radio communications can either speed up the communications by transmitting the message to all neighbors or slow down the communications because of the conflicts with other transmissions. Thus, it is crucial to devise the conflict-free broadcast schedule, especially in mobile ad hoc networks on 3D space. Additionally, as most real networks are dynamic, it is also challenging to develop online algorithms for the broadcast scheduling with a good performance.
Objectives: