Search

The social presence theory in social psychology suggests that computer-mediated online interactions are inferior to face-to-face, in-person interactions. In this paper, we consider the scenarios of organizing in person friend-making social activities via online social networks (OSNs) and formulate a new research problem, namely, Hop-bounded Maximum Group Friending (HMGF), that takes into consideration both existing friendships and the likelihood of new friend making in organization of the targeted in person friend-making social activities. To find a set of attendees for such social activities, HMGF is unique and challenging due to the interplay of the group size, the constraint on existing friendships, and the objective of maximizing the likelihood of friend making. We propose an error-bounded approximation algorithm, MaxGF, to efficiently obtain the solutions very close to the optimal solutions. To boost the performance, we devise two graph-theoretical pruning strategies, namely Neighbor Pruning and Core Pruning, which can effectively avoid redundant graph explorations to improve the performance of HMGF. We conduct a user study to validate our problem formulation and perform extensive experiments on real datasets to demonstrate the efficiency and effectiveness of our proposed algorithm. The experimental results manifest that our proposed algorithms outperform the baselines, including the ILP formulation.

Viral marketing on social networks, also known as Influence Maximization (IM), aims to select k users for the promotion of a target item by maximizing the total spread of their influence. However, most previous works on IM do not explore the dynamic user perception of promoted items in the process. In this paper, by exploiting the knowledge graph (KG) to capture dynamic user perception, we formulate the problem of Influence Maximization based on Dynamic Personal Perception (IMDPP) that considers user preferences and social influence reflecting the impact of relevant item adoptions. We prove the hardness of IMDPP and design an approximation algorithm, named Dynamic perception for seeding in target markets (Dysim), by exploring the concepts of dynamic reachability, target markets, and substantial influence to select and promote a sequence of relevant items. We evaluate the performance of Dysim in comparison with the state-of-the-art approaches using real social networks with real KGs. The experimental results show that Dysim effectively achieves at least 6 times of influence spread in large datasets over the state-of-the-art approaches.

Research suggests that social relationships have substantial impacts on individuals' health outcomes. Network intervention, through careful planning, can assist a network of users to build healthy relationships. However, most previous work is not designed to assist such planning by carefully examining and improving multiple network characteristics. In this paper, we propose and evaluate algorithms that facilitate network intervention planning through simultaneous optimization of network degree, closeness, betweenness, and local clustering coefficient, under scenarios involving Network Intervention with Limited Degradation - for Single target (NILD-S) and Network Intervention with Limited Degradation - for Multiple targets (NILD-M). We prove that NILD-S and NILD-M are NP-hard and cannot be approximated within any ratio in polynomial time unless P=NP. We propose the Candidate Re-selection with Preserved Dependency (CRPD) algorithm for NILD-S, and the Objective-aware Intervention edge Selection and Adjustment (OISA) algorithm for NILD-M. Various pruning strategies are designed to boost the efficiency of the proposed algorithms. Extensive experiments on various real social networks collected from public schools and Web and an empirical study are conducted to show that CRPD and OISA outperform the baselines in both efficiency and effectiveness.

Because Online Social Networks (OSNs) have become increasingly important in the last decade, they have motivated a great deal of research on Social Network Analysis (SNA). Currently, SNA algorithms are evaluated on real datasets obtained from large-scale OSNs, which are usually sampled by Breadth-First-Search (BFS), Random Walk (RW), or some variations of the latter. However, none of the released datasets provides any statistical guarantees on the difference between the sampled datasets and the ground truth. Moreover, all existing sampling algorithms only focus on sampling a single OSN, but each OSN is actually a sampling of a complete social network. Hence, even if the whole dataset from a single OSN is sampled, the results may still be skewed and may not fully reflect the properties of the complete social network. To address the above issues, we have made the first attempt to explore the joint sampling of multiple OSNs and propose an approach called Quality-guaranteed Multi-network Sampler (QMSampler) that can jointly sample multiple OSNs. QMSampler provides a statistical guarantee on the difference between the sampled real dataset and the ground truth (the perfect integration of all OSNs). Our experimental results demonstrate that the proposed approach generates a much smaller bias than any existing method. QMSampler has also been released as a free download.

Spatial proximity is one of the most important factors for the quick deployment of the task groups in various time-sensitive missions. This article proposes a new spatial query, Spatio-Social Team Query (SSTQ) , that forms a strong task group by considering (1) the group’s spatial distance (i.e., transportation time), (2) skills of the candidate group members, and (3) social rapport among the candidates. Efficient processing of SSTQ is very challenging, because the aforementioned spatial, skill, and social factors need to be carefully examined. In this article, therefore, we first formulate two subproblems of SSTQ, namely Hop-Constrained Team Problem (HCTP) and Connection-Oriented Team Query (COTQ) . HCTP is a decision problem that considers only social and skill dimensions. We prove that HCTP is NP-Complete. Moreover, based on the hardness of HCTP, we prove that SSTQ is NP-Hard and inapproximable within any factor . On the other hand, COTQ is a special case of SSTQ that relaxes the social constraint. We prove that COTQ is NP-Hard and propose an approximation algorithm for COTQ, namely COTprox . Furthermore, based on the observations on COTprox, we devise an approximation algorithm, SSTprox , with a guaranteed error bound for SSTQ. Finally, to efficiently obtain the optimal solution to SSTQ for small instances, we design two efficient algorithms, SpatialFirst and SkillFirst , with different scenarios in mind. These two algorithms incorporate various effective ordering and pruning techniques to reduce the search space for answering SSTQ. Experimental results on real datasets indicate that the proposed algorithms can efficiently answer SSTQ under various parameter settings.

Studies show that a person is willing to join a social group activity if the activity is interesting, and if some close friends also join the activity as companions. The literature has demonstrated that the interests of a person and the social tightness among friends can be effectively derived and mined from social networking websites. However, even with the above two kinds of information widely available, social group activities still need to be coordinated manually, and the process is tedious and time-consuming for users, especially for a large social group activity, due to complications of social connectivity and the diversity of possible interests among friends. To address the above important need, this paper proposes to automatically select and recommend potential attendees of a social group activity, which could be very useful for social networking websites as a value-added service. We first formulate a new problem, named Willingness mAximization for Social grOup (WASO). This paper points out that the solution obtained by a greedy algorithm is likely to be trapped in a local optimal solution. Thus, we design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users.

Depth-Image-Based Rendering (DIBR) is a popular technology and enables the viewers to watch multi-view 3D videos via TV or smart phone. In this paper, we propose a game-theoretical framework over a multi-view and multi-video network where one server delivers multiple multi-view 3D videos to multiple viewers. In a mobile network, any individual viewers can subscribe to a video with any viewing angle within a specified viewing range in 3D-enabled mobile handsets. To facilitate efficient resource allocation for multi-view 3D videos, we formulate a new resource allocation problem, named Price-based 3D Viewing Range Control problem (PVRC), as a Stackelberg game in Game Theory, in which the server and the viewers are modeled as the leader and the followers, respectively, to jointly consider the revenue of the server and the utilities of the viewers. We analyze the price setting problem by investigating the Stackelberg equilibrium between the server and viewers. Simulation results demonstrate that compared to popular uniform-price setting, non-uniform pricing is an effective approach for reducing the difference of utilities among the viewers, effectively controlling the viewing ranges and avoiding starvation of the network resources to only few viewers. Moreover, we also derive the social optimum in the problem, and the simulation results show that the derived Stackelberg equilibrium is close to the social optimum.

Management of uncertain data in spatial queries has drawn extensive research interests to consider the granularity of devices and noises in the collection and the delivery of data. Most previous works usually model and handle uncertain data to find the required results directly. However, it is more difficult for users to obtain useful insights when data uncertainty dramatically increases. In this case, users are usually willing to invest more resources to improve the result by reducing the data uncertainty in order to obtain more interesting observations with the existing schemes. In light of this important need, this paper formulates a new problem of selecting a given number of uncertain data objects for acquiring their attribute values to improve the result of the Probabilistic k-Nearest-Neighbor (k-PNN) query. We prove that better query results are guaranteed to be returned with data acquisition, and we devise several algorithms to maximize the expected improvement. We first explore the optimal single-object acquisition for 1-PNN to examine the fundamental problem structure and then propose an efficient algorithm that discovers crucial properties to simplify the probability derivation in varied situations. We extend the proposed algorithm to achieve the optimal multi-object acquisition for 1-PNN by deriving an upper bound to facilitate efficient pruning of unnecessary sets of objects. Moreover, for data acquisition of k-PNN, we extract the k-PNN answers with sufficiently large probabilities to trim the search space and properly exploit the result of single-object acquisition for estimating the gain from multi-object acquisition. The experimental results demonstrate that the probability of k-PNN can be significantly improved even with only a small number of objects for data acquisition.

Software-Defined Networking and Network Function Virtualisation (SDN/NFV) can provide flexible resource allocation to support innovative security solutions in a central manner. To mitigate HTTP DDoS attacks, shuffling-based moving target defense has been regarded as one of the most effective ways by redirecting user traffic among a group of virtualized service functions. However, previous work did not notice that frequent changes of user traffic will significantly intensify the control overhead of SDN. In this paper, therefore, we first model the effectiveness and cost for shuffling in SDN/NFV networking with Multi-Objective Markov Decision Processes to find the optimal tradeoff between the effectiveness and cost. We then propose a cost-effective approximation algorithm with a guarantee performance bound to solve the problem. Simulation and implementation on an experimental SDN/NFV network manifest that, given 100 attackers among 1000 users and 50 virtualized functions of a web service, our algorithm achieves the approximation ratio of 0.68 and imposes only 2.4s rule modification latency for each shuffle.

An increasing number of social network mental disorders (SNMDs), such as Cyber-Relationship Addiction, Information Overload, and Net Compulsion, have been recently noted. Symptoms of these mental disorders are usually observed passively today, resulting in delayed clinical intervention. In this paper, we argue that mining online social behavior provides an opportunity to actively identify SNMDs at an early stage. It is challenging to detect SNMDs because the mental factors considered in standard diagnostic criteria (questionnaire) cannot be observed from online social activity logs. Our approach, new and innovative to the practice of SNMD detection, does not rely on self-revealing of those mental factors via questionnaires. Instead, we propose a machine learning framework, namely, Social Network Mental Disorder Detection (SNMDD), that exploits features extracted from social network data to accurately identify potential cases of SNMDs. We also exploit multi-source learning in SNMDD and propose a new SNMD-based Tensor Model (STM) to improve the performance. Our framework is evaluated via a user study with 3126 online social network users. We conduct a feature analysis, and also apply SNMDD on large-scale datasets and analyze the characteristics of the three SNMD types. The results show that SNMDD is promising for identifying online social network users with potential SNMDs., Comment: 11 pages

With the emergence of 3D mobile and VR devices, mobile 3D video services are becoming increasingly important for video service providers, such as Youtube and Netflix, while multi-view 3D videos have the potential to inspire a variety of innovative applications. However, enabling multi- view 3D video services may overwhelm WiFi networks when every view of a video are multicasted. In this paper, therefore, we propose to leverage depth-image-based rendering (DIBR) in multi-view 3D, which allows each mobile client to synthesize the desired view from nearby left and right views, in order to effectively reduce the bandwidth consumption. Moreover, when each client suffers from packet losses, retransmissions incur additional bandwidth consumption and excess delay, which in turn undermines the quality of experience in video applications. To address the above issue, we first discover the merit of view protection via DIBR for multi-view video multicast using a mathematical analysis and then design a new protocol, named Multi-View Group Management Protocol (MVGMP), to support the dynamic join and leave of users and the change of desired views. The simulation results demonstrate that our protocol effectively reduces bandwidth consumption and increases the probability for each client to successfully playback the desired views in a multi-view 3D video.

It might not seem dangerous for a person to leave some pieces of personal information on the Internet since everyone tends to do this. But the truth is that if someone ever tries to collect those pieces of information together, he might be able to find out the true identity of the person in reality after analyzing the collected data, which is what we call “cyber hunting”. This work focuses on the question of “what kind(s) of personal information will lead to a higher risk of personal re-identification on the Internet?” To answer this question, we conducted a case study of PTT-and-FB linkage and share effective suggestions for Internet users to avoid being cyber hunted. At the end of this work, we found that the three attributes of gender, birthday and location are more sensitive compared to other attributes and users should prevent themselves from providing these kinds of information to secure their privacy.

Various typing methods of qwerty-based keyboards on smartwatches have been proposed in recent years. However, since each key can only occupy limited input space and our fingers are too big, recent solutions are mainly two-step typing methods. Users have to navigate the desired key on an enlarged keyboard, and then select the target. The two-step process is distant from our physical keyboard experiences, and requires users to frequently change the keyboard layouts. The aim of this paper is to propose a single-step typing technique that allows users to key in a character with a single touch. We introduce ForceBoard, which combines two adjacent keys into one region and uses force as selecting mechanism. By using that, it not only provides more precise selection, but also allows users to type texts without changing the visual contents of keyboard. We conducted a study comparing the performance of ForceBoard with other two state-of-the-art two-step methods, ZoomBoard and SplitBoard. Our results showed that ForceBoard outperformed ZoomBoard significantly with 30.52% on average, and was slightly better than SplitBoard. Furthermore, ForceBoard also received higher preferences on text speed and satisfaction.

The skyline query, aiming at identifying a set of skyline tuples that are not dominated by any other tuple, is particularly useful for multicriteria data analysis and decision making. For uncertain databases, a probabilistic skyline query, called P-Skyline, has been developed to return skyline tuples by specifying a probability threshold. However, the answer obtained via a P-Skyline query usually includes skyline tuples undesirably dominating each other when a small threshold is specified; or it may contain much fewer skyline tuples if a larger threshold is employed. To address this concern, we propose a new uncertain skyline query, called U-Skyline query, in this paper. Instead of setting a probabilistic threshold to qualify each skyline tuple independently, the U-Skyline query searches for a set of tuples that has the highest probability (aggregated from all possible scenarios) as the skyline answer. In order to answer U-Skyline queries efficiently, we propose a number of optimization techniques for query processing, including 1) computational simplification of U-Skyline probability, 2) pruning of unqualified candidate skylines and early termination of query processing, 3) reduction of the input data set, and 4) partition and conquest of the reduced data set. We perform a comprehensive performance evaluation on our algorithm and an alternative approach that formulates the U-Skyline processing problem by integer programming. Experimental results demonstrate that our algorithm is 10-100 times faster than using CPLEX, a parallel integer programming solver, to answer the U-Skyline query.

Research issues and data mining techniques for product recommendation and viral marketing have been widely studied. Existing works on seed selection in social networks do not take into account the effect of product recommendations in e-commerce stores. In this paper, we investigate the seed selection problem for viral marketing that considers both effects of social influence and item inference (for product recommendation). We develop a new model, Social Item Graph (SIG), that captures both effects in form of hyperedges. Accordingly, we formulate a seed selection problem, called Social Item Maximization Problem (SIMP), and prove the hardness of SIMP. We design an efficient algorithm with performance guarantee, called Hyperedge-Aware Greedy (HAG), for SIMP and develop a new index structure, called SIG-index, to accelerate the computation of diffusion process in HAG. Moreover, to construct realistic SIG models for SIMP, we develop a statistical inference based framework to learn the weights of hyperedges from data. Finally, we perform a comprehensive evaluation on our proposals with various baselines. Experimental result validates our ideas and demonstrates the effectiveness and efficiency of the proposed model and algorithms over baselines., Comment: 12 pages

Deep packet filtering (DPF) has been demonstrated as an essential technique for effective fine-grained access controls, but it is commonly recognized that the technique may invade the individual privacy of the users. Secure computation can address the tradeoff between privacy and DPF functionality, but the current solutions limit the scalability of the network due to the intensive computation overheads and large connection setup delay, especially for the latest network paradigm, network function virtualisation (NFV) and software-defined network (SDN). In this paper, therefore, we propose a privacy-preserving deep packet filtering protocol, named DPF-ET, that can efficiently perform filtering function over encrypted traffic while diminishing the communication overhead and setup delay for the controller in SDN. DPF-ET guarantees the data privacy for users and remains rule privacy for the network owner. The implementation results on an experimental HP SDN/NFV platform demonstrate that the proposed DPF-ET outperforms the current approaches by reducing 250 times in the communications overhead and 32 times in the setup delay.

Inspired by the coming of data-driven innovation and economy, an increasing number of companies over the world are eager to analyze their data for creating useful knowledge, while graph data have become more and more crucial in many areas, such as social networks and medical/chemical applications. Different from conventional transaction data, finding the frequent patterns in a graph is more challenging because graph structures are much more flexible and generalized, and various algorithms have been proposed to properly cope with different graph data. However, for companies and organizations without sophisticated and experienced data scientists, it is usually difficult for them to properly choose a graph mining algorithm that is the most efficient and effective one for their own data. When an inadequate algorithm is employed, excess processing time is usually incurred, and important large patterns may not always be able to be generated. To address the above important need, this paper proposes a new mechanism, referred to as GMRecommend, for recommending a proper graph mining algorithm given the graph data with specific features. GMRecommend is based on support vector machine (SVM) by incorporating two important categories of features: graph features and pattern features. Experimental results manifest that GMRecommend can effectively choose the most proper graph mining algorithm for different kinds of graph data with different characteristics and requirements.

In this paper, we first study an important but unsolved dilemma in the literature of subspace clustering, which is referred to as ldquoinformation overlapping-data coveragerdquo challenge. Current solutions of subspace clustering usually invoke a grid-based apriori-like procedure to identify dense regions and construct subspace clusters afterward. Due to the nature of monotonicity property in apriori-like procedures, it is inherent that if a region is identified as dense, all its projected regions are also identified as dense, causing overlapping/redundant clustering information to be inevitably reported to users when generating clusters from such highly correlated regions. However, naive methods to filter redundant clusters will incur a challenging problem in the other side of the dilemma, called the ldquodata coveragerdquo issue. Note that two clusters may have highly correlated dense regions but their data members could be highly different to each other. Arbitrarily removing one of them may lose the coverage of data with clustering information, thus likely reporting an incomplete and biased clustering result. In this paper, therefore, we further propose an innovative algorithm, called "nonredundant subspace cluster miningrdquo (NORSC), to efficiently discover a succinct collection of subspace clusters while also maintaining the required degree of data coverage. NORSC not only avoids generating the redundant clusters with most of the contained data covered by higher dimensional clusters to resolve the information overlapping problem but also limits the information loss to cope with the data coverage problem. As shown by our experimental results, NORSC is very effective in identifying a concise and small set of subspace clusters, while incurring time complexity in orders of magnitude better than that of previous works.

The development and integration of social networking services and smartphones have made it easy for individuals to organize impromptu social activities anywhere and anytime. Main challenges arising in organizing impromptu activities are mostly due to the requirements of making timely invitations in accordance with the potential activity locations, corresponding to the locations of, and the relationships among the candidate attendees. Various combinations of candidate attendees and activity locations create a large solution space. Thus, in this paper, we propose Multiple Rally-Point Social Spatial Group Query (MRGQ), to select an appropriate activity location for a group of nearby attendees with tight social relationships. We first consider a special case of MRGQ, namely the Socio-Spatial Group Query (SSGQ), to determine a set of socially acquainted attendees while minimizing the total spatial distance to a specific activity location. We prove that SSGQ is NP-hard and formulate an Integer Linear Programming optimization model for SSGQ. We then develop an efficient algorithm, called SSGS, which employs effective pruning techniques to reduce the running time to determine the optimal solution. Moreover, we propose a heuristic algorithm for SSGQ to efficiently produce good solutions. We next consider the more general MRGQ. Although MRGQ is NP-hard, the number of attendees in practice is usually small enough such that an optimal solution can be found efficiently. Therefore, we first propose an Integer Linear Programming optimization model for MRGQ. We then design an efficient algorithm, called MAGS, which employs effective search space exploration and pruning strategies to reduce the running time for finding the optimal solution. We also propose to further optimize efficiency by indexing the potential activity locations. A user study demonstrates the strength of using SSGS and MAGS over manual coordination in terms of both solution quality and efficiency. Experimental results on real datasets show that our algorithms can process SSGQ and MRGQ efficiently and significantly outperform other baseline algorithms, including one based on the commercial parallel optimizer IBM CPLEX.

Studies have shown that each person is more inclined to enjoy a group activity when 1) she is interested in the activity, and 2) many friends with the same interest join it as well. Nevertheless, even with the interest and social tightness information available in online social networks, nowadays many social group activities still need to be coordinated manually. In this paper, therefore, we first formulate a new problem, named Participant Selection for Group Activity (PSGA), to decide the group size and select proper participants so that the sum of personal interests and social tightness of the participants in the group is maximized, while the activity cost is also carefully examined. To solve the problem, we design a new randomized algorithm, named Budget-Aware Randomized Group Selection (BARGS), to optimally allocate the computation budgets for effective selection of the group size and participants, and we prove that BARGS can acquire the solution with a guaranteed performance bound. The proposed algorithm was implemented in Facebook, and experimental results demonstrate that social groups generated by the proposed algorithm significantly outperform the baseline solutions.

Business-location planning, critical to the success of many businesses, can be addressed by the reverse nearest neighbors (RNN) query using geographical proximity to the customers as the main metric to find a store location close to many customers. Nevertheless, we argue that other marketing factors, such as social influence, could be considered in the process of business-location planning. In this article, we propose a framework for business-location planning that takes into account both factors of geographical proximity and social influence . An essential task in this framework is to compute the “influence spread” of RNNs for candidate locations. Here, the influence spread refers to the number of people influenced via the word-of-mouth effect. To alleviate the excessive computational overhead and long latency in the framework, we trade storage overhead for processing speed by precomputing and storing the social influence between pairs of customers. Based on Targeted Region (TR)-Oriented and RNN-Oriented processing strategies, we develop two suites of algorithms that incorporate various efficient pruning and segmentation techniques to enhance our framework. Experiments validate our ideas and evaluate the efficiency of the proposed algorithms over various parameter settings. The experimental results show that (a) TR-oriented and RNN-oriented processing are feasible for supporting the task of location planning; (b) RNN-oriented processing is more efficient than TR-oriented processing; and (c) the optimization technique that we developed significantly improves the efficiency of RNN-oriented and TR-oriented processing.

Real datasets always play an essential role in graph mining and analysis. However, nowadays most available real datasets only support millions of nodes. Therefore, the literature on Big Data analysis utilizes statistical graph generators to generate a massive graph (e.g., billions of nodes) for evaluating the scalability of an algorithm. Nevertheless, current popular statistical graph generators are properly designed to preserve only the statistical metrics, such as the degree distribution, diameter, and clustering coefficient of the original social graphs. Recently, the importance of frequent graph patterns has been recognized in the various works on graph mining, but unfortunately this crucial criterion has not been noticed in the existing graph generators. To address this important need, we make the first attempt to design a Pattern Preserving Graph Generation (PPGG) algorithm to generate a graph including all frequent patterns and three most popular statistical parameters: degree distribution, clustering coefficient, and average vertex degree. The experimental results show that PPGG, which we have released as a free download, is efficient and able to generate a billion-node graph in approximately 10 minutes, much faster than the existing graph generators.

Studies show that both the personal preference and social tightness between friends play important roles in the decision process of activity participation for a person. Considering the preference of a person and the social tightness among friends, in this work, we formulate a new research problem, called Package Organization for Willingness satisfaction (POWA), to effectively select items into a package that can be adopted by the most users. Efficiently obtaining the optimal package and the corresponding group of users under the setting of POWA is very challenging, as we prove that POWA is NP-hard. Aiming to strike a balance between the quality of solutions and the time needed for computation, we propose algorithm Intermediate Package Organization with Social and Preference Pruning (IPOSPP) to obtain good solutions efficiently. We conduct an extensive performance evaluation on four real datasets to demonstrate the performance of the proposed algorithm.

Mining big graph data is an important problem in the graph mining research area. Although cloud computing is effective at solving traditional algorithm problems, mining frequent patterns of a massive graph with cloud computing still faces the three challenges: 1) the graph partition problem, 2) asymmetry of information, and 3) pattern-preservation merging. Therefore, this paper presents a new approach, the cloud-based SpiderMine (c-SpiderMine), which exploits cloud computing to process the mining of large patterns on big graph data. The proposed method addresses the above issues for implementing a big graph data mining algorithm in the cloud. We conduct the experiments with three real data sets, and the experimental results demonstrate that c-SpiderMine can significantly reduce execution time with high scalability in dealing with big data in the cloud.

To many location-based service applications that prefer diverse results, finding locations that are spatially diverse and close in proximity to a query point (e.g., the current location of a user) can be more useful than finding the k nearest neighbors/locations. In this paper, we investigate the problem of searching for the k Diverse-Near Neighbors (kDNNs)} in spatial space that is based upon the spatial diversity and proximity of candidate locations to the query point. While employing a conventional distance measure for proximity, we develop a new and intuitive diversity metric based upon the variance of the angles among the candidate locations with respect to the query point. Accordingly, we create a dynamic programming algorithm that finds the optimal kDNNs. Unfortunately, the dynamic programming algorithm, with a time complexity of O(kn3), incurs excessive computational cost. Therefore, we further propose two heuristic algorithms, namely, Distance-based Browsing (DistBrow) and Diversity-based Browsing (DivBrow) that provide high effectiveness while being efficient by exploring the search space prioritized upon the proximity to the query point and spatial diversity, respectively. Using real and synthetic datasets, we conduct a comprehensive performance evaluation. The results show that DistBrow and DivBrow have superior effectiveness compared to state-of-the-art algorithms while maintaining high efficiency.

Due to the rich information in graph data, the technique for privacy protection in published social networks is still in its infancy, as compared to the protection in relational databases. In this paper we identify a new type of attack called a friendship attack. In a friendship attack, an adversary utilizes the degrees of two vertices connected by an edge to re-identify related victims in a published social network data set. To protect against such attacks, we introduce the concept of k2-degree anonymity, which limits the probability of a vertex being re-identified to 1/k. For the k2-degree anonymization problem, we propose an Integer Programming formulation to find optimal solutions in small-scale networks. We also present an efficient heuristic approach for anonymizing large-scale social networks against friendship attacks. The experimental results demonstrate that the proposed approaches can preserve much of the characteristics of social networks.

In recent years, data uncertainty widely attracts researchers' attention because the amount of imprecise data is growing rapidly. Although data are not known exactly, probability distributions or expected errors are sometimes available. While most researchers on uncertain data mining are looking for methods to extract mining results from uncertain data, which is usually in the form of probability distributions or expected errors, it is also very important to lower the data uncertainty by making a part of data more certain to help get better mining results. For example, input values of some sensors in the sensor network are usually designed to be recorded more frequently than others because they are more important or more likely to change. In this paper, the issue of selecting a part of uncertain data and acquiring their exact values to improve clustering results is explored. Under a general uncertainty model, we propose both global and localized data selection methods, which can be used together with any existing uncertain clustering algorithm. Experimental results show that the quality of clustering improves after the selective exact value acquisition is applied.

In this paper, we investigate and utilize the characteristic of the group movement of objects to achieve energy conservation in the inherently resource-constrained wireless object tracking sensor network (OTSN). We propose a novel mining algorithm that consists of a global mining and a local mining to leverage the group moving pattern. We use the VMM model together with Probabilistic Suffix Tree (PST) in learning the moving patterns, as well as Highly Connected Component (HCS) that is a clustering algorithm based on graph connectivity for moving pattern clustering in our mining algorithm. Based on the mined out group relationship and the group moving patterns, a hierarchically prediction-based query algorithm and a group data aggregation algorithm are proposed. Our experiment results show that the energy consumption in terms of the communication cost for our system is better than that of the conventional query/update based OTSN, especially in the case that on-tracking objects have the group moving characteristics.

This paper studies the integration of multimedia multicasting, with the consideration of multicast with end-to-end QoS guarantees by resource reservation, dynamic join and departure of participants, user heterogeneity, scalability, robustness, and loop-free control. A protocol called MQ, Multicast with QoS, is proposed to support multimedia group communications with QoS guarantees for heterogeneous recipients. With MQ, while resource reservation is de-coupled from QoS multicast routing, they are integrated in a way to avoid the problem of "sender-oriented" path determination, a problem that occurs when RSVP is used in conjunction with QoS routing for heterogeneous reservations. Being a truly receiver-oriented and integrated scheme for multimedia multicasting, MQ supports such integration in a robust, scalable and loop-free way. It also accommodates heterogeneous users with varied QoS, dynamically adjusts QoS trees to improve resource utilization, and guarantees end-to-end QoS requirements. We have conducted simulations to evaluate the performance of the proposed mechanism. MQ demonstrates its advantages over the conventional loosely coupled integration of TP multicasting, resource reservation and QoS routing, in terms of better accommodation of heterogeneous users, higher scalability, lower blocking probability for users to join groups with service guarantees, and more efficient resource utilization to enhance system performance.