My research interests are centered on the Combinatorial Optimization and its connection to Networks, including communication networks, online social networks, wireless sensor networks, and biological networks. More specifically, the focus of my research is to design and analyze several new models and approximation algorithms for various fundamental problems, arising from the networking fields mentioned above. These studies have led into many beautiful yet challenging problems and results in theory, which enrich other computer science and mathematical areas, such as graph theory and approximation algorithms. Recently, I have been working on the fundamental models and basic theories for the design of complex and social-aware information networks. The following are some of my recent research projects, which are supported by NSF 0847869, NSF CAREER 0953284, DTRA YIP HDTRA1-09-1-0061, and DTRA HDTRA1-08-10.

For more information, please visit my research lab: Optima Network Science

Motivation: 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. Furthermore, this vulnerability may be propagated, leading to a much more devastating consequence. A failure within a single component may have a profound impact on large parts of the system. The nodes' failures may change the balance of flows and lead to a global redistribution of loads over the entire network. This can trigger a cascade of overload failures. Thus it is very crucial to investigate the network vulnerability wrt cascading failures and critical nodes which are important to be protected. In addition, many networks including the WWW, the Internet, Power-grid network exhibit the power-law degree distribution, which may contribute a significant impact on investigate many important properties of complex networks.

Objectives:

Provide optimization models and solutions to identify the critical nodes/location of the networks under different measurement metrics such as connectivity and QoS

Analyze how network structures impact the inter- and intra-dependency of networks components and between networks

Investigate how vulnerability propagates under different diffusion models based on network structures

Design robustly connected networks that efficiently respond to massive localized outages and WMD attacks via approximation and game theories

Investigate what role the power-law distribution plays in the complexity and approximation of solutions

Investigate the hardness complexity and devise constant approximation algorithms for several optimization problems that exploit the power-law distribution

Selected Publication:

T. N. Dinh, Y. Xuan, M. T. Thai, EK Park, and T. Znati, On Approximation of New Optimization Methods for Assessing Network Vulnerability, in Proceedings of the IEEE Communications Society (INFOCOM), 2010

M. T. Thai, T. N. Dinh, and Y. Shen, Hardness and Approximation of Network Vulnerability, Handbook of Combinatorial Optimization, (P. Pardalos, D.-Z. Du, and R. Graham eds), Springer Publisher

Y. Shen, N. P. Nguyen, and M. T. Thai, Exploiting the Robustness on Power-Law Networks, in Proceedings of the 17th Int Computing and Combinatorics Conference (COCOON), 2011

Motivation: Several communication networks, such as online social networks and cellular networks, exhibit a deep interplay between the physical and the social networks involved. Thus studying the properties of the social networks is necessary to understand and reason about those communication networks. It also provides a better solution for communication technologies that consider social context by explicitly incorporating human values at multiple levels and scale into the design.

Objectives:

Investigate several optimization problems of which the underlying topology are social networks, such as worm containment in cellular networks, routing protocols in DTN or MANETs

Construct and analyze a social relationship graph of mobile devices and online social networks based on their communication patterns; analyze online communities

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

Selected Publication:

T. N. Dinh, D. T. Nguyen, and M. T. Thai, Cheap, Easy, and Massively Effective Viral Marketing in Social Networks: Truth or Fiction?, in Proceedings of ACM Conference on Hypertext and Social Media (Hypertext), 2012

Y. Shen, Y-S. Syu, D. T. Nguyen, and M. T. Thai, Maximizing Circle of Trust in Online Social Networks, in Proceedings of ACM Conference on Hypertext and Social Media (Hypertext), 2012

N. P. Nguyen, G. Yan, M. T. Thai, and S. Eidenbenz, Containment of Viral Spread in Online Social Networks, in Proceedings of ACM Web Science (WebSci), 2012

N. P. Nguyen, T. N. Dinh, S. Tokala, and M. T. Thai, Overlapping Communities in Dynamic Networks: Their Detection and Mobile Applications, in Proceedings of ACM International Conference on Mobile Computing and Networking (MobiCom), 2011

N. P. Nguyen, T. N. Dinh, Y. Xuan, and M. T. Thai, Adaptive Algorithms for Detecting Community Structure in Dynamic Social Networks, in Proceedings of the IEEE Communications Society (INFOCOM), 2011

Motivation: Due to network failures/uncertainties and dynamics, several network algorithms must be adaptable to changes in order to maintain their functions. For example, changes in a network topology may cause the reconfiguration of any routing algorithm since the previous routing path may no longer be available. Of course, the simplest and naive way is to recompute a new routing path from scratch for every changes. However, doing so may result in prohibitive computational complexity, particularly in the case of highly dynamic networks. A natural attempt to reduce the computational costs after a change would be to update the routing path based on the previous path since a portion of this path can be reused. The solution which is updated from the previous one is called an adaptive solution. However, it is quite challenging to design such a solution, especially which guarantees the performance bound.

Objectives:

Provide models to characterize quantitative benefits of using adaptive solutions vs. re-computing it from scratch

Develop adaptive algorithms for dynamics and evolving networks

Devise new approximation techniques for adaptive solutions in order to theoretically bound their performance

Motivation: One of the most critical problems in network security is the Denial-of-Service (DoS) attack, which aims to make a service unavailable to legitimate clients. Since malicious requests can be made arbitrarily similar to legitimate ones, accurately and efficiently distinguishing them is a challenging task for any defense mechanism. As a result, efficiently identifying the attackers in service-level DoS attacks, becomes much more difficult. Similarly, DoS attacks, such as a jamming attack is one of the most low-cost and intelligent attacks yet fatally adversarial threats in wireless sensor networks as they attack the broadcast nature of transmission mediums. (The jammers will stay idle until they sense some transmission going on and start injecting noises to jam the current transmission.) As sensor devices have low computation capacities and are battery powered, it is quite challenging to design an efficient defense strategy for this attack.

Objectives:

Provide new models and solutions against reactive jamming attacks by identifying trigger nodes whose transmissions invoke the jammer. The triggers identification approach utilizes a hexagon tiling coloring and Group Testing (GT) techniques in a completely localized manner

Devise new construction of d-disjunct matrix to effectively utilize the group testing theory. Develop randomized error-tolerant non-adaptive group testing technique

Provide models and solutions to identify malicious users and application DoS attacks without inspecting each traffic one by one

Selected Publication:

Y. Xuan, Y. Shen, N. P. Nguyen, and M. T. Thai, A Trigger Identification Service for Defending Reactive Jammers in WSNs, IEEE Transactions on Mobile Computing (TMC), 2011

Y. Xuan, I. Shin, M. T. Thai, and T. Znati, Detecting Application Denial-of-Service Attacks: A Group Testing Based Approach, IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, pp. 1203-1216, 2010

M. T. Thai and T. Znati, On the Complexity and Approximation of Non-unique Probe Selection Using d-Disjunct Matrix, Journal of Combinatorial Optimization, special issues on Data Mining in Biomedicine, vol. 17, no. 1, pp 45-53, 2009

M. T. Thai, Y. Xuan, I. Shin, and T. Znati, On Detection of Malicious Users Using Group Testing Techniques, in Proceedings of Int. Conf. on Distributed Computing Systems (ICDCS), 2008

H. Gao, F.K. Hwang, M. T. Thai, W. Wu, and T. Znati, Construction of d(H)-Disjunt Matrix for Group Testing in Hypergraphs, J. of Combinatorial Optimization, vol. 12, no. 3, pp. 297-301, 2006

Motivation: Broadcasts and multicasts are two main methods of communications in wireless networks. As mentioned, energy efficiency and interference-free are the two most concerned factors in wireless networks among many performance metrics. It is thus important to devise new broadcast/multicasts protocols to minimize the energy consumption while guaranteeing the interference-free.

Objectives:

Develop virtual backbone assisted routing algorithms based on the concept of connected dominating set (CDS); Study the CDS problem and its variants on different network topologies

Provide a more practical and realistic model to capture all interference scenarios; devise constant approximation algorithms and efficient heuristic for broadcast scheduling in 2D and 3D

Selected Publication:

R. Tiwari, T. N. Dinh, and M. T. Thai, On Approximation Algorithms for Interfence-Aware Broadcast Scheduling in 2D and 3D Wireless Sensor Networks, in Proceedings of Int. Conf. on Wireless Algorithms, Systems and Applications (WASA), 2009

R. Mahiourian, F. Chen, R. Tiwari, M. T. Thai, H. Zhai, and Y. Feng, An Approximation Algorithm for Conflict-Aware Broadcast Scheduling in Wireless Ad Hoc Networks, in Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2008

M. T. Thai, R. Tiwari, and D.-Z. Du, On Construction of Virtual Backbone in Wireless Ad Hoc Networks with Unidirectional Links, IEEE Transactions on Mobile Computing (TMC), vol. 7, no. 8, pp. 1-12, 2008

M. T. Thai, N. Zhang, R. Tiwari, and X. Xu, On Approximation Algorithms of k-Connected m-Dominating Sets in Disk Graphs, Theoretical Computer Science, vol. 385, no. 1-3, pp. 49-59, 2007

M. T. Thai, F. Wang, D. Liu, S. Zhu, and D.-Z. Du, Connected Dominating Sets in Wireless Networks with Different Transmission Ranges, IEEE Transactions on Mobile Computing (TMC), vol. 6, no. 7, July, 2007

F. Wang, M. T. Thai, Y. Li, X. Cheng, and D.-Z. Du, Fault Tolerant Topology Control for All-to-One and One-to-All Communication in Wireless Networks, IEEE Transaction on Mobile Computing (TMC), vol. 7, no. 3, pp. 322-331, 2007

Y. Li, M. T. Thai, F. Wang, and D.-Z. Du, On the Construction of a Strongly Connected Broadcast Arborescence with Bounded Transmission Delay, IEEE Transactions on Mobile Computing (TMC), vol. 5,  no. 10, pp. 1460-1470, 2006

Motivation: With recent advances in technology, applying and using Wireless Sensor Networks (WSNs) in our daily lives in the next decades are no longer a dream, but a reality. By utilizing WSNs, several phenomenon such as oil leakage, movements of groups can be monitored and tracking. An important problem in such monitor is to guarantee a full coverage under any circumstances for any shape and motion of cloud phenomenon. Unfortunately, these shapes are variant, from concave to convex, and highly dynamic. In addition, sensor nodes are battery powered and have a limited weight. Thus it is critical to design energy efficient protocols to prolong network lifetime while guaranteeing the complete coverage and accurate detection/tracking.

Objectives:

Devise approximation algorithms with a good performance ratio and practical algorithms, i.e., distributed and localized algorithms, for the coverage problem

Develop new models and in-network detection and tracking techniques for either static or dynamic cloud phenomenon which have variant shapes

Selected Publication:

D. T. Nguyen, N. P. Nguyen, M. T. Thai, and S. Helal, On Optimal Algorithm for Coverage Hole Healing in Hybrid Sensor Networks, in Proceedings of the IEEE Int Wireless Communications and Mobile Computing conference (IWCMC), 2011

R. Tiwari, M. T. Thai, and S. Helal, Localized Energy Efficient Detection and Tracking of Dynamic Phenomena, in Proceedings of the IEEE Global Communication Conference, (GLOBECOM), 2010

M. T. Thai, Y. Li, F. Wang, and D.-Z. Du, O(log n)-Localized Algorithms on the Coverage Problem in Heterogeneous Sensor Networks, in Proceedings of the 26^th IEEE International Performance Computing and Communications Conference (IPCCC 2007), April, 2007

M. Cardei, M. T. Thai, Y. Li, and W. Wu, Energy-Efficient Target Coverage in Wireless Sensor Networks, in Proceedings of the 24^th conference of the IEEE Communications Society (INFOCOM 2005), March 2005