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
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.
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:
- . “TipTop: Almost Exact Solutions for Influence Maximization in Billion-Scale Networks,” in IEEE/ACM Transactions on Networking, 2019
- . “Influence Maximization at Community Level: A New Challenge with Non-Submodularity,” in IEEE ICDCS, 2019
- . “Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice,” in Proceedings of ICML, 2018
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
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:
- . “Adaptive Crawling with Multiple Bots: A Matroid Intersection Approach,” in Proceedings of INFOCOM, 2018
- . “An Approximately Optimal Bot for Non-Submodular Social Reconnaissance,” in Proceedings of HyperText, 2018
- . “Adaptive Reconnaissance Attacks with Near-Optimal Parallel Batching,” in Proceedings of ICDCS, 2017
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
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:
- . “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
- . “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
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:
- . “Catastrophic Cascading Failures in Power Networks,” in Theoretical Computer Science, 2015