Modeling and Analysis of Multiplex Social Networks

Overlapping users of social networks such as Facebook and Twitter link these online social networks into a multiplex of social networks. As different components of the multiplex may have different properties, the multiplex may exhibit emergent phenomena that isn’t present in the simpler case of single layer social networks. For example, diffusion is likely to occur by different processes and with different speeds; therefore, one problem we consider is the diffusion of influence in a heterogeneous multiplex: where each layer has a different model of diffusion. Given this heterogenity of diffusion, new approaches to problems such as Influence Maximiation (IM) and Threshold Activation Problem (TAP) may be necessary.

Objectives:

  • Determine emergent phenomena arising from the added multiplex complexity
  • Study heterogeneous diffusion processes and related problems
  • Study problems where the diffusion speed are different for networks

Selected Publications:

  • H. Zhang, D. T. Nguyen, S. Das, H. Zhang, and M. T. Thai. “Least Cost Influence Maximization Across Multiple Social Networks,” in IEEE Transactions on Networking (ToN), 2015
  • D. T. Nguyen, H. Zhang, S. Das, M. T. Thai, and T. N. Dinh. “Least Cost Influence in Multiplex Social Networks: Model Representation and Analysis,” in Proceedings of the IEEE Int Conference on Data Mining (ICDM), 2013

Vulnerability in Interdependent Networks

The study of interdependent networks from the perspective of vulnerability seeks to identify the critical elements with respect to a variety of measures. An interdependent system is robust if external perturbations do not significantly impair the functionality of the system. In this area, we seek to design methods to identify the critical elements. One measure we study in general interdependent networks is the vulnerability of network clustering to node failure. We also study measures in practical scenarios, one scenario is in a Smart Grid system, how the interdependent communication and power networks impact one another’s functionality -- a failure in one of these networks may cascade to the other. Another scenario is in mobile social networks underlay a D2D network, where misinformation in the social network may cascade and cause users stop using D2D, thus impact the throughput of the D2D network.

Objectives:

  • Characterize robustness using a variety of measures of functionality
  • Study interdependency effects relevant to vulnerability, such as cascading failure
  • Identify critical elements in the functionality of interdependent systems

Selected Publications:

  • D. T. Nguyen, Y. Shen, and M. T. Thai. “Detecting Critical Nodes in Interdependent Power Networks for Vulnerability Assessment,” in IEEE Transactions on Smart Grid (ToSG), 2013

Influence Maximization & Misinformation Countermeasures

Online social networks (OSNs) like Facebook, Twitter, etc. are excellent media for viral marketing. One of the fundamental problems for viral marketing in OSNs is the influence maximization (IM) problem, where the company aims at reaching a widespread product adoption via word-of-mouth effect by providing free samples of a product to a set of influential individuals. In a graph G, IM can be restate as finding at most k seed nodes (influential individuals) that can influence the maximum number of nodes, either directly or indirectly. A variation of IM, the threshold activation problem (TAP), does not restrict the number of seed nodes. Instead, it aims at using minimum number of seed nodes to influence at least fraction of all nodes. As the graph is usually gigantic and also probabilistic, exact solutions to neither IM or TAP are accessible with reasonable computational resources. Thus, the solutions rely on sampling methods and the main objective of research is to design approaches to use less samples while maintaining solution quality.

Objectives:

  • Design efficient sampling methods for estimating influence spread in large-scale OSNs
  • Study variations of IM, TAP (for example: by considering external influence or different diffusion models)

Selected Publications:

  • Xiang Li, J David Smith, Thang Dinh, and My T. Thai. “Why approximate when you can get the exact? Optimal Targeted Viral Marketing at Scale.,” in Proceedings of the IEEE Int Conference on Computer Communications (INFOCOM), 2017 [arXiv]
  • H. Zhang, H. Zhang, A. Kuhnle, and and M. T. Thai. “Profit Maximization for Multiple Products in Online Social Networks,” in Proceedings of the IEEE Int Conference on Computer Communications (INFOCOM), 2016
  • H. T. Nguyen, M. T. Thai, and T. N. Dinh. “Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks,” in Proceedings of ACM SIGMOD/POSD Conference (SIGMOD), 2016

Sybil attack and limiting the spread of misinformation

The wide spread of misinformation in online social networks has become a main threat to our society. Generally, people tend to believe what their friends are saying. Leveraging the social relationships to contain or block the misinformation appears to be a promising strategy.

Objectives:

  • Detect misinformation in online social networks in the early stage of spread
  • Design effective measure to evaluate the nodes contribution of diffuse the true information in the presence of misinformation
  • Identify the most important nodes in the spread of true information so as to block the misinformation

Selected Publications:

  • Huiling Zhang, Alan Kuhnle, Huiyuan Zhang, and My T. Thai. “Detecting Misinformation in Online Social Networks Before It Is Too Late,” in The 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2016), 2016
  • N. P. Nguyen, G. Yan, and M. T. Thai. “Analysis of Misinformation Containment in Online Social Networks,” in Elsevier Computer Networks-Towards a Science of Cyber Security (COMNETS), vol. 57, no. 10, pp. 2133--2146, 2013

Socialbot Behavior & Detection

The socialbot attack model is a spiritual successor to the Sybil attack model that addresses several of its flaws. Where the Sybil model makes strong assumptions about the number and organization of the attackers, the socialbot model relaxes those. A socialbot is simply a bot that pretends to be a human on a social network. Therefore, a socialbot attack could consist of only a single attacker or an army of loosely-coordinated assailants.

Objectives:

  • Devise theoretically optimal socialbot attacks, and study their limitations and how to exploit them for defense.
  • Examine the impact of user behaviors on socialbot attacks, and study how attackers may exploit or suffer from these behaviors.

Selected Publications:

  • Xiang Li, J David Smith, and My T. Thai. “Adaptive Reconnaissance Attacks with Near-Optimal Parallel Batching,” in Proceedings of ICDCS, 2017
  • Xiang Li, J David Smith, Thang N. Dinh, and My T. Thai. “Privacy Issues in Light of Reconnaissance Attacks with Incomplete Information,” in IEEE/WIC/ACM International Conference on Web Intelligence (WI), 2016

Socially Aware Schemes to Offload Network Traffic

Although Device-to-device (D2D) communications over licensed wireless spectrum has been recently proposed as a promising technology to meet the capacity crunch of next generation cellular networks, the success, to a large extent, depends on the willingness of the participating devices to share their resources. Consideration of social aspect of human communication can go a long way in extracting efficient solutions to offload cellular traffic. However, due to the high mobility of cellular devices, establishing and ensuring the success of D2D transmission becomes a major challenge. Social aware community based approaches are shown to be useful in identifying a set of reliable relay devices that help a content to be transmitted from a source/cache to a destination.

Objectives:

  • Devise novel framework to form multi-hop D2D connections in an effort to maximize time sensitive real-time content delivery
  • Design a practical model to predict devise mobility coupled with physical radio network design aspects for transmitting delay-sensitive content
  • Devise efficient multicast scheme to leverage similar content request in a particular location for offloading base station traffic

Vulnerabilities in Socially-Enabled Smart Grid

The social computing will integrate and enhance many digital systems over the next decade and the smart grid is no exception. Smart grid efficiency depends on utility customers having knowledge about demand response programs and being actively engaged in energy management. And this is exactly where social network comes into the picture and can really have an impact. Social computing can also expand the adoption and adaptation of smart grid technologies through the peer to peer communication in local communities through social network. It also could change large scale behavior through crowdshifting basing on the theory "people decide how to behave based on what they see others doing, especially if those others seem similar to themselves".

Objectives:

  • Study and analyze the inter dependency between social network and smart grid
  • Explore possible vulnerabilities and corresponding protection measures in the socially enabled smart grid

Selected Publications:

  • S. Mishra, J. Seo, X. Li, and M. T. Thai. “Catastrophic Cascading Failures in Power Networks,” in Theoretical Computer Science, 2015

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

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.

Objectives:

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

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

Spectral Efficiency and Resource Management

In cellular networks, rapid increase of data consumption has strained the network infrustructure. Proximity based device-to-device communication has been introduced as a way forward in next generation LTE networks. However, assigning limited resources efficiently to enable maximum reuse with spectral efficiency still remains an important challenge. As devices enter and leave a network frequently in an online manner, the solution framework must be able to work adaptively. The resource allocation algorithm should be fast and light because of the instantaneous nature of ever increasing content demand.

Objectives:

  • Propose efficient resource reuse scheme considering inband interference management between cellular and D2D users.
  • Design online and adaptive algorithm with performance guarantee for resource allocation in D2D underlaying cellular network
  • Suggest new ways to incorporate social aware encounter based information in designing and identifying proper devices that facilitate maximum resource utilization

Selected Publications:

  • Alan Kuhnle, Xiang Li, J David Smith, and My T. Thai. “Online set multicover algorithms for dynamic D2D communications,” in Journal of Combinatorial Optimization, 2017
  • A. Kuhnle, X. Li, and M. T. Thai. “Online Algorithms for Optimal Resource Management in Dynamic D2D Communications,” in Proceedings of the IEEE 10th International Conference on Mobile Ad-hoc and Sensor Networks (MSN), 2014

Socially Aware Schemes to Offload Network Traffic

Although Device-to-device (D2D) communications over licensed wireless spectrum has been recently proposed as a promising technology to meet the capacity crunch of next generation cellular networks, the success, to a large extent, depends on the willingness of the participating devices to share their resources. Consideration of social aspect of human communication can go a long way in extracting efficient solutions to offload cellular traffic. However, due to the high mobility of cellular devices, establishing and ensuring the success of D2D transmission becomes a major challenge. Social aware community based approaches are shown to be useful in identifying a set of reliable relay devices that help a content to be transmitted from a source/cache to a destination.

Objectives:

  • Devise novel framework to form multi-hop D2D connections in an effort to maximize time sensitive real-time content delivery
  • Design a practical model to predict devise mobility coupled with physical radio network design aspects for transmitting delay-sensitive content
  • Devise efficient multicast scheme to leverage similar content request in a particular location for offloading base station traffic

Sybil attack and limiting the spread of misinformation

The wide spread of misinformation in online social networks has become a main threat to our society. Generally, people tend to believe what their friends are saying. Leveraging the social relationships to contain or block the misinformation appears to be a promising strategy.

Objectives:

  • Detect misinformation in online social networks in the early stage of spread
  • Design effective measure to evaluate the nodes contribution of diffuse the true information in the presence of misinformation
  • Identify the most important nodes in the spread of true information so as to block the misinformation

Selected Publications:

  • Huiling Zhang, Alan Kuhnle, Huiyuan Zhang, and My T. Thai. “Detecting Misinformation in Online Social Networks Before It Is Too Late,” in The 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2016), 2016
  • N. P. Nguyen, G. Yan, and M. T. Thai. “Analysis of Misinformation Containment in Online Social Networks,” in Elsevier Computer Networks-Towards a Science of Cyber Security (COMNETS), vol. 57, no. 10, pp. 2133--2146, 2013

Socialbot Behavior & Detection

The socialbot attack model is a spiritual successor to the Sybil attack model that addresses several of its flaws. Where the Sybil model makes strong assumptions about the number and organization of the attackers, the socialbot model relaxes those. A socialbot is simply a bot that pretends to be a human on a social network. Therefore, a socialbot attack could consist of only a single attacker or an army of loosely-coordinated assailants.

Objectives:

  • Devise theoretically optimal socialbot attacks, and study their limitations and how to exploit them for defense.
  • Examine the impact of user behaviors on socialbot attacks, and study how attackers may exploit or suffer from these behaviors.

Selected Publications:

  • Xiang Li, J David Smith, and My T. Thai. “Adaptive Reconnaissance Attacks with Near-Optimal Parallel Batching,” in Proceedings of ICDCS, 2017
  • Xiang Li, J David Smith, Thang N. Dinh, and My T. Thai. “Privacy Issues in Light of Reconnaissance Attacks with Incomplete Information,” in IEEE/WIC/ACM International Conference on Web Intelligence (WI), 2016

Vulnerabilities in Socially-Enabled Smart Grid

The social computing will integrate and enhance many digital systems over the next decade and the smart grid is no exception. Smart grid efficiency depends on utility customers having knowledge about demand response programs and being actively engaged in energy management. And this is exactly where social network comes into the picture and can really have an impact. Social computing can also expand the adoption and adaptation of smart grid technologies through the peer to peer communication in local communities through social network. It also could change large scale behavior through crowdshifting basing on the theory "people decide how to behave based on what they see others doing, especially if those others seem similar to themselves".

Objectives:

  • Study and analyze the inter dependency between social network and smart grid
  • Explore possible vulnerabilities and corresponding protection measures in the socially enabled smart grid

Selected Publications:

  • S. Mishra, J. Seo, X. Li, and M. T. Thai. “Catastrophic Cascading Failures in Power Networks,” in Theoretical Computer Science, 2015

Price Modification and Load Distribution Attacks

Smart Grid addresses the problem of existing powergrid\'s increasing complexity, growing demand and requirement for greater reliability, through two-way communication and automated residential load control among others. These features also makes the Smart Grid a target for a number of cyber attacks. The load profiles of consumers could be changed through the fabrication of price messages. This attack could lead to cascading failures. Our work is the first attempt to study the effect of such cyber attacks on smart grid, seeking the vulnerable critical nodes. With linearized DC power flow model and cascading failure in power grid models, we also provide solutions to mitigate or reduce the damage due to the cascading failures.

Objectives:

  • Find vulnerable nodes where price modification attacks have potential to cause large blackouts
  • Find measures to mitigate the cascading failures due to price modification attacks

Selected Publications:

  • S. Mishra, X .Li, T. Pan, A. Kuhnle, M. T. Thai, and J. Seo. “Price Modification Attack and Protection Scheme in Smart Grid,” in IEEE Transactions on Smart Grid, 2016
  • S. Mishra, X. Li, A. Kuhnle, M. T. Thai, and J. Seo. “Rate Alteration Attacks in Smart Grid,” in Proceedings of the IEEE Int Conference on Computer Communications (INFOCOM), 2015
  • S. Mishra, X. Li, M. T. Thai, and J. Seo. “Cascading Critical Nodes Detection with Load Redistribution in Complex Systems,” in Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2014

Complex Network Vulnerability Assessment

The study of network vulnerability seeks to identify the critical elements with respect to a variety of measures. Generally speaking, a network is robust if external pertubations do not significantly impair its functionality. In this area, we seek to design methods to identify the critical elements. One measure we study is the vulnerability of network clustering to node failure; another is the vulnerability of Quality of Service (QoS) in a communication network to node and link failures.

Objectives:

  • Identify critical elements for network infrastructure measurements, such as the degree of network clustering
  • Design comprehensive vulnerability measure for communication networks capable of utilizing any QoS metric

Selected Publications:

  • T. N. Dinh and M. T. Thai. “Assessing Attack Vulnerability in Networks with Uncertainty,” in Proceedings of the IEEE Int Conference on Computer Communications (INFOCOM), 2015
  • Md A. Alim, A. Kuhnle, and M. T. Thai. “Are Communities As Strong As We Think?,” in Proceedings of IEEE/ACM Int Conf on Advances in Social Networks Analysis and Mining (ASONAM), 2014
  • T. N. Dinh, M. T. Thai, and H. Nguyen. “Bound and Exact Methods for Assessing Link Vulnerability in Complex Networks,” in Journal of Combinatorial Optimization, 2014

Vulnerability in Interdependent Networks

The study of interdependent networks from the perspective of vulnerability seeks to identify the critical elements with respect to a variety of measures. An interdependent system is robust if external perturbations do not significantly impair the functionality of the system. In this area, we seek to design methods to identify the critical elements. One measure we study in general interdependent networks is the vulnerability of network clustering to node failure. We also study measures in practical scenarios, one scenario is in a Smart Grid system, how the interdependent communication and power networks impact one another’s functionality -- a failure in one of these networks may cascade to the other. Another scenario is in mobile social networks underlay a D2D network, where misinformation in the social network may cascade and cause users stop using D2D, thus impact the throughput of the D2D network.

Objectives:

  • Characterize robustness using a variety of measures of functionality
  • Study interdependency effects relevant to vulnerability, such as cascading failure
  • Identify critical elements in the functionality of interdependent systems

Selected Publications:

  • D. T. Nguyen, Y. Shen, and M. T. Thai. “Detecting Critical Nodes in Interdependent Power Networks for Vulnerability Assessment,” in IEEE Transactions on Smart Grid (ToSG), 2013

SCADA and DPI

Supervisory Control And Data Acquisition (SCADA) system remotely monitors and controls remote stations from a central SCADA center through coded signals over communication (or control) network. The addition of control network to better manage and gather system data comes with its own set of vulnerabilities including false data injection and fabricated system data which leads to bad state estimation. Among security enhancements such as advanced encryption and authentication, deep packet inspection (DPI) is used to detect malicious packets. However, DPI introduces delay in the poacket transmission in highly time critical IEC 61850 messages. Our work focus on the placement of the DPIs in the control network in order to maximize the amount of scanned packets.

Objectives:

  • To optimally place the DPIs in the control network without violating the time delay constraint
  • Investigate other ways to detect malicious packets in SCADA network

Selected Publications:

  • S. Mishra, T. N. Dinh, M. T. Thai, and I. Shin. “Optimal Inspection Points for Malicious Attack Detection in Smart Grids,” in Proceedings of the 20th Int Computing and Combinatorics Conference (COCOON), 2014

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

Vulnerabilities in Socially-Enabled Smart Grid

The social computing will integrate and enhance many digital systems over the next decade and the smart grid is no exception. Smart grid efficiency depends on utility customers having knowledge about demand response programs and being actively engaged in energy management. And this is exactly where social network comes into the picture and can really have an impact. Social computing can also expand the adoption and adaptation of smart grid technologies through the peer to peer communication in local communities through social network. It also could change large scale behavior through crowdshifting basing on the theory "people decide how to behave based on what they see others doing, especially if those others seem similar to themselves".

Objectives:

  • Study and analyze the inter dependency between social network and smart grid
  • Explore possible vulnerabilities and corresponding protection measures in the socially enabled smart grid

Selected Publications:

  • S. Mishra, J. Seo, X. Li, and M. T. Thai. “Catastrophic Cascading Failures in Power Networks,” in Theoretical Computer Science, 2015

Price Modification and Load Distribution Attacks

Smart Grid addresses the problem of existing powergrid\'s increasing complexity, growing demand and requirement for greater reliability, through two-way communication and automated residential load control among others. These features also makes the Smart Grid a target for a number of cyber attacks. The load profiles of consumers could be changed through the fabrication of price messages. This attack could lead to cascading failures. Our work is the first attempt to study the effect of such cyber attacks on smart grid, seeking the vulnerable critical nodes. With linearized DC power flow model and cascading failure in power grid models, we also provide solutions to mitigate or reduce the damage due to the cascading failures.

Objectives:

  • Find vulnerable nodes where price modification attacks have potential to cause large blackouts
  • Find measures to mitigate the cascading failures due to price modification attacks

Selected Publications:

  • S. Mishra, X .Li, T. Pan, A. Kuhnle, M. T. Thai, and J. Seo. “Price Modification Attack and Protection Scheme in Smart Grid,” in IEEE Transactions on Smart Grid, 2016
  • S. Mishra, X. Li, A. Kuhnle, M. T. Thai, and J. Seo. “Rate Alteration Attacks in Smart Grid,” in Proceedings of the IEEE Int Conference on Computer Communications (INFOCOM), 2015
  • S. Mishra, X. Li, M. T. Thai, and J. Seo. “Cascading Critical Nodes Detection with Load Redistribution in Complex Systems,” in Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2014

SCADA and DPI

Supervisory Control And Data Acquisition (SCADA) system remotely monitors and controls remote stations from a central SCADA center through coded signals over communication (or control) network. The addition of control network to better manage and gather system data comes with its own set of vulnerabilities including false data injection and fabricated system data which leads to bad state estimation. Among security enhancements such as advanced encryption and authentication, deep packet inspection (DPI) is used to detect malicious packets. However, DPI introduces delay in the poacket transmission in highly time critical IEC 61850 messages. Our work focus on the placement of the DPIs in the control network in order to maximize the amount of scanned packets.

Objectives:

  • To optimally place the DPIs in the control network without violating the time delay constraint
  • Investigate other ways to detect malicious packets in SCADA network

Selected Publications:

  • S. Mishra, T. N. Dinh, M. T. Thai, and I. Shin. “Optimal Inspection Points for Malicious Attack Detection in Smart Grids,” in Proceedings of the 20th Int Computing and Combinatorics Conference (COCOON), 2014

Influence Maximization & Misinformation Countermeasures

Online social networks (OSNs) like Facebook, Twitter, etc. are excellent media for viral marketing. One of the fundamental problems for viral marketing in OSNs is the influence maximization (IM) problem, where the company aims at reaching a widespread product adoption via word-of-mouth effect by providing free samples of a product to a set of influential individuals. In a graph G, IM can be restate as finding at most k seed nodes (influential individuals) that can influence the maximum number of nodes, either directly or indirectly. A variation of IM, the threshold activation problem (TAP), does not restrict the number of seed nodes. Instead, it aims at using minimum number of seed nodes to influence at least fraction of all nodes. As the graph is usually gigantic and also probabilistic, exact solutions to neither IM or TAP are accessible with reasonable computational resources. Thus, the solutions rely on sampling methods and the main objective of research is to design approaches to use less samples while maintaining solution quality.

Objectives:

  • Design efficient sampling methods for estimating influence spread in large-scale OSNs
  • Study variations of IM, TAP (for example: by considering external influence or different diffusion models)

Selected Publications:

  • Xiang Li, J David Smith, Thang Dinh, and My T. Thai. “Why approximate when you can get the exact? Optimal Targeted Viral Marketing at Scale.,” in Proceedings of the IEEE Int Conference on Computer Communications (INFOCOM), 2017 [arXiv]
  • H. Zhang, H. Zhang, A. Kuhnle, and and M. T. Thai. “Profit Maximization for Multiple Products in Online Social Networks,” in Proceedings of the IEEE Int Conference on Computer Communications (INFOCOM), 2016
  • H. T. Nguyen, M. T. Thai, and T. N. Dinh. “Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks,” in Proceedings of ACM SIGMOD/POSD Conference (SIGMOD), 2016

Modeling and Analysis of Multiplex Social Networks

Overlapping users of social networks such as Facebook and Twitter link these online social networks into a multiplex of social networks. As different components of the multiplex may have different properties, the multiplex may exhibit emergent phenomena that isn’t present in the simpler case of single layer social networks. For example, diffusion is likely to occur by different processes and with different speeds; therefore, one problem we consider is the diffusion of influence in a heterogeneous multiplex: where each layer has a different model of diffusion. Given this heterogenity of diffusion, new approaches to problems such as Influence Maximiation (IM) and Threshold Activation Problem (TAP) may be necessary.

Objectives:

  • Determine emergent phenomena arising from the added multiplex complexity
  • Study heterogeneous diffusion processes and related problems
  • Study problems where the diffusion speed are different for networks

Selected Publications:

  • H. Zhang, D. T. Nguyen, S. Das, H. Zhang, and M. T. Thai. “Least Cost Influence Maximization Across Multiple Social Networks,” in IEEE Transactions on Networking (ToN), 2015
  • D. T. Nguyen, H. Zhang, S. Das, M. T. Thai, and T. N. Dinh. “Least Cost Influence in Multiplex Social Networks: Model Representation and Analysis,” in Proceedings of the IEEE Int Conference on Data Mining (ICDM), 2013

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

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:

  • From theoretical facet, improve Group Testing models and algorithms to enhance the affection detection efficiency
  • Combine the developed Group Testing models with Graph Theory, Learning Theory to tackle wired application-layer DoS attacks and wireless reactive Jamming attacks
  • Provide efficient routing scheme for unreliable networks, in order to maximize pairwise routing packet delivery ratio and avoid congestions

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:

  • Propose the quality measure to evaluate the coverage quality of wireless sensor networks
  • Design fast and light movement scheduling algorithm that relocate mobile sensors to guarantee a specific coverage quality

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:

  • Devise constant approximation algorithms for broadcast scheduling in mobile ad hoc networks on 3D space
  • Design a practical model to cover all interference and mobility scenarios in dynamic networks
  • Devise online scheduling algorithms for broadcast in dynamic networks

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:

  • Design faster algorithms to solve several optimization problems that exploit the power law distribution
  • Revisit the hardness results of several problems on the new type of networks
  • Re-analyze existing solutions on the new network models capturing the power law property