Search

Black box has been an important tool in studying computational complexity theory and has been used for establishing the hardness of problems. With an exponential growth in big data recently, data-driven computation has utilized black box as a tool for proving solutions to some computational problems. In this note, we present several observations on this new role of black box using reduction techniques in the computational complexity theory.

Electronic Health Record (EHR) has been widely adopted in the US in the past decade, which provides an increasing interest for predictive analysis with clinical time series data. Recently, deep learning approaches such as Recurrent Neural Network (RNN) and attention based networks have achieved the state-of-the-art accuracy on several clinical time series tasks, but one shortcoming of the RNN is the slow processing due to its sequential nature. In this paper, we propose a Filter based Feature Engineering method and a two-phase auto hyperparameter optimization method, which fit very well to clinical time series scenario. Combined with two widely used tree boosting methods: XGBoost and LightGBM, we demonstrated that our approach achieved the state-of-the-art results with more than 100X speed acceleration compared with RNN methods on two MIMIC-III benchmark tasks: In Hospital Mortality Prediction and 25-Phenotype Classification. Due to its superior accuracy and faster speed advantages, our approach has broad clinical application prospect, especially assisting doctors to make right diagnosis and treatment prognosis in shorter invaluable time.

The sensor is often supplied with electrical power. For sensors studied in previous chapters, the electrical power comes from batteries, which have limited lifetime. Therefore, several technologies for recharging batteries have been developed recently. Such technologies utilize energy sources in environment, such as sunlight, electromagnetic radiation, thermal, and vibration. A sensor with such a technology is called the energy-harvesting sensor, that is, an energy-harvesting sensor is able to convert energy of other types, in environment, to electrical energy. Among other energy sources, the sunlight is the most available one outdoor. Solar technologies are developed quite fast and now already reach conversion efficiency of 15%.

The connected sensor cover was first studied by Cardei et al. The minimum connected sensor cover problem (Problem 1.3.2) was first proposed by Gupta, Das, and Gu. They presented a greedy algorithm with performance ratio \(O(r \ln n)\) where n is the number of sensors and r is the link radius of the sensor network, i.e., for any two sensors s and s′ with a sensing point in common, there exists a path between s and s′ with hop distance at most r in communication network. Zhang and Hou studied the minimum connected sensor cover problem in homogeneous wireless sensor networks with property that Rc ≥ 2Rs. They showed that in this case, the coverage of a connected target area implies the connectivity. This result was generalized by Zhou, Das, and Gupta to the m-connectivity that if every point in a connected target area is covered by at least m sensors, then those sensors induce an m-connected sensor network. Xing et al. presented a coverage configuration protocol which can give different degree of coverage requested by applications. Bai et al. studied a sensor deployment problem regarding the coverage and connectivity. Alam and Haas studied this problem in three-dimensional sensor networks.

When a very large number of sensors are randomly deployed into a region by an aircraft in order to monitor a certain set of targets (target points), there are often a lot of redundant sensors. A better usage of those redundant sensors is to make a sleep/wakeup scheduling for sensors, which would increase the lifetime of coverage. The lifetime of coverage is the length of a time period at every moment of which every target is monitored by an active sensor.

Online social networks have many benefits as a medium for fast, widespread information dissemination. They provide fast access to large-scale news data, sometimes even before the mass media. They also serve as a medium to collectively achieve a social goal. For instance with the use of group and event pages in Facebook, events such as Day of Action protests reached thousands of protestors. While the ease of information propagation in social networks can be very beneficial, it can also have disruptive effects. One such example was observed in August 2012, thousands of people in Ghazni province left their houses in the middle of the night in panic after the rumor of earthquake. Another example is the fast spread of misinformation in twitter that the president of Syria is dead, leading to a sharp, quick increase in the price of oil. There are lots of similar examples. Although social networks are the main source of news for many people today, they are not considered reliable due to such problems.

Cascading processes are models of network diffusion used to study phenomenon concerning the spread of new trends and innovations in social networks. Each node can be in one of two states: infected (i.e., supports an idea or a product) or uninfected. Every infected node can infect its neighbors and thus, the infection, formally called a cascade, propagates through the network. These processes have been studied in many applications such as viral marketing, blog networks, and contagion models.

The rising popularity of online social networks has made information generating and sharing much easier than ever before, due to the ability to publish content to large, targeted audiences. Such networks enable their participants to simultaneously become both consumers and producers of content, shifting the role of information broker from a few dedicated entities to a diverse and distributed group of individuals. While this fundamental change allows information propagating at an unprecedented rate, it also enables unreliable or unverified information spreading among people, such as rumors.

A large amount of data are stored in geographically distributed data centers interconnected by the Internet. The power consumption for running the servers storing the data and inter-data center network transport for data update among the multiple data copies stored in different data centers impose a significant operational cost on cloud service providers. Few research places data replicas in the data centers by jointly taking both electricity consumption and network transport into account under the user access latency requirement constraints. However, there is an intrinsic tradeoff between the electricity consumption of the data centers and the network transport cost for data update. In this paper, we tackle the problem of data placement in data centers with the aim to minimize the operational cost under user access latency requirements, assuming all the data have K copies. We propose an effective algorithm, Latency-aware and operational Cost minimization Data Placement (LCDP), which partitions the data into multiple data groups according to the data access rates and greedily selects K data centers incurring the minimum cost for each data in each data group. We prove that algorithm LCDP is \(\frac{1}{2} \ln |\mathrm {U}|\)-approximation to the data placement problem, where \(|\mathrm {U}|\) is the number of users. Our simulation results demonstrate that the proposed algorithm can effectively reduce the power consumption cost, the network transport cost, and the operational cost of the data centers.

With the great advantage of information spread in the social network, more and more team activities would like to be organized through the social platforms. These activities require users to match partners and then participate in groups, e.g., group-buying and blind-date. In this paper, we consider to organize such activities with matching constraints in social networks to attract as many matched participants as possible through a limited seed set. An Interest-based Forwarding model which is similar to Independent Cascading is used to model information propagation. We investigate two matching strategies to forming groups: (1) neighbor matching (NM), i.e., only direct neighbors can match and (2) global matching (GM), i.e., matching is organized by an external organizer. We prove the matched participants maximization (MPM) problem to optimize the seed set selection to maximize the expected number of final participants is NP-hard and the computation of the target function is #P-hard, under both the NM and GM strategies. To solve MPM-NM efficiently, we propose a Matching Reachable Set method and a \((1-1/e-\epsilon )\)-approximation algorithm. Sandwich method is used for solving MPM-GM by using the result of MPM-NM as a lower-bound and constructing an upper bound in an extended graph. A \(\beta (1 - 1/e-\epsilon )\)-approximation algorithm is proposed for MPM-GM. At last, experiments on the real-world databases verifies the effectiveness and efficiency of the proposed algorithms.

Even though the widespread use of social networks brings a lot of convenience to people’s life, it also cause a lot of negative effects. The spread of misinformation in social networks would lead to public panic and even serious economic or political crisis. We study the community-based rumor blocking problem to select b seed users as protectors such that expected number of users eventually not being influenced by rumor sources is maximized, called Community-based Rumor Blocking Maximization Problem (CRBMP). We consider the community structure in the social network and solve our problem in two stages, in the first stage, we allocate budget b for all the communities with the technique of submodular function maximization on an integer lattice, which is different from most of the existing work with the submodular function over a set function. We prove that the objective function for the budget allocation problem is monotone and DR-submodular, then a greedy algorithm is devised to get a \(1-1/e\) approximation ratio; then we solve the Protector Seed Selection (PSS) problem in the second stage after we obtained the budget allocation vector for communities, we greedily choose protectors for each communities with the budget constraints to achieve the maximization of the influence of protectors. The greedy algorithm for PSS problem can achieve a \(\frac{1}{2}\)-approximation guarantee. At last, we verified the effectiveness and superiority of our algorithms on three real world datasets .

With the emergence and rapid proliferation of social applications and media, such as instant messaging (e.g., WhatsApp, Viber, WeChat, Snapchat, Line, Facebook Messenger, and Google Hangouts), sharing sites (e.g., Flickr, YouTube, and Yelp), blogs (e.g., WordPress and LiveJournal), wikis (e.g., Wikipedia and PBWiki), microblogs (e.g., Twitter and Weibo), social networks (e.g., Facebook), and collaboration networks (e.g., DBLP), there is little doubt that social influence is becoming a prevalent, complex, and subtle force that governs the dynamics of all social networks. Therefore, social influence study has started to attract intense attention due to many important applications.

In this chapter, we outline the techniques used in optimizing or facilitating information diffusion in social networks. We identify two problem definitions through which a broad survey of techniques in recent research is provided. Namely, we explore the problems of maximizing the spread of influence and minimizing the spread of misinformation in social networks. As different as these problems are in terms of the motivation behind them, they both rely on sub-problems that are very similar. Through our study of these two problems, we delve into more detail about the sub-problems: Sect. 2.2 model formation, Sect. 2.3 problem optimization, Sect. 2.4 large-scale data analysis, and Sect. 2.5 research trends.

For applications in agriculture, sensors are often placed at grid points. Which grid (or pattern) minimizes the number of sensors and reach the full (area) coverage? It is not hard to show that the optimal solution is the triangle grid such that each cell is an equilateral triangle. However, when the requirement is the full coverage together with others, such as k-connectivity, the optimal solution would be nontrivial. Actually, there exist a lot of research efforts along this direction in the literature.

Multi-document summarization deals with finding the core theme presented in multiple documents. This can be done by selecting the important information from the text in the multiple documents. Extractive summarization selects and extracts such sentences which represent the gist of the documents. In this paper, we have surveyed how research in multi-document summarization has evolved from simple sentence-based techniques like sentence position to complex neural network based supervised learning techniques. In recent years, more and more supervised learning methods are proposed to tackle this problem along with some unsupervised approaches described in LSA (Deerwester et al. J Am Soc Inf Sci 41(6): 391–407, 1990) and TextRank (Mihalcea et al. Textrank: Bringing order into text. In: Proceedings of the 2004 conference on empirical methods in natural language processing, 2004). In this chapter, we have proposed an alternative unsupervised method where the problem of multi-document summarization can be viewed as a non-linear combinatorial optimization problem. We have formulated the problem and discussed possible solution to this problem.

Data-dependent approximation is a new approach for the study of nonsubmodular optimization problems. This approach has attracted a lot of research especially in the area of social computing, where nonsubmodular combinatorial optimization problems have been recently formulated. In this chapter, we present some theoretical results on the data-dependent approximation approach. In addition, some related open problems are discussed.

People with the same interests, hobbies or political orientation always form a group to share all kinds of topics in Online Social Networks (OSN). Product producers often hire the OSN provider to propagate their advertisements in order to influence all possible potential groups. In this paper, a group is assumed to be activated if \(\beta \) percent of members are activated. Product producers will gain revenue from all activated groups through group-buying behavior. Meanwhile, to propagate influence, producers need pay diffusion cost to the OSN provider, while the cost is usually relevant to total hits on the advertisements. We aim to select k seed users to maximize the expected profit that combines the benefit of activated groups with the diffusion cost of influence propagation, which is called Group Profit Maximization (GPM) problem. The information diffusion model is based on Independent Cascade (IC), and we prove GPM is NP-hard and the objective function is neither submodular nor supermodular. We develop an upper bound and a lower bound that both are difference of two submodular functions. Then we design an Submodular-Modular Algorithm (SMA) for solving difference of submodular functions and SMA is proved to converge to local optimal. Further, we present an randomized algorithm based on weighted group coverage maximization for GPM and apply Sandwich framework to get theoretical results. Our experiments verify the effectiveness of our method, as well as the advantage of our method against the other heuristic methods.

Influence maximization problem has been studied extensively with the development of online social networks. Most of the existing works focus on the maximization of influence spread under the assumption that the number of influenced users determines the success of a product promotion. However, the profit of some products such as online game depends on the interactions among users besides the number of users. In this paper, we take both the number of active users and the user-to-user interactions into account and propose the interaction-aware influence maximization problem. To address this practical issue, we analyze its complexity and modularity, propose the sandwich theory which is based on decomposing the non-submodular objective function into the difference of two submodular functions and design iterated sandwich algorithm which is guaranteed to get data dependent approximation solution.

Influence maximization problem is among the most important topics in the area of social networking, it has attracted a lot of research work. Recently, the influence maximization problem has been extended to practical scenarios. In this chapter, we present one cutting-edge problem named interaction-aware influence maximization, which involves nonsubmodular optimization.