Group extraction from professional social network using a new semi-supervised hierarchical clustering

Recently, social network has been given much attention. This paper addresses the issue of extraction groups from professional social network and enriches the representation of the user profile and its related groups through building a social network warehousing. Several criteria may be applied to detect groups within professional communities, such as the area of expertise, the job openings proposed by the group, the security of the group, and the time of the group creation. In this paper, we aim to find, extract, and fuse the LinkedIn users. Indeed, we deal with the group extraction of LinkedIn users based on their profiles using our innovative semi-supervised clustering method based on quantitative constraints ranking. The encouraging experimental results carried out on our real professional warehouse show the usefulness of our approach.     

Detecting and predicting privacy violations in online social networks

Online social networks have become an essential part of social and work life. They enable users to share, discuss, and create content together with various others. Obviously, not all content is meant to be seen by all. It is extremely important to ensure that content is only shown to those that are approved by the content’s owner so that the owner’s privacy is preserved. Generally, online social networks are promising to preserve privacy through privacy agreements, but still everyday new privacy leakages are taking place. Ideally, online social networks should be able to manage and maintain their agreements through well-founded methods. However, the dynamic nature of the online social networks is making it difficult to keep private information contained. We have developed $\mathcal{PROTOSS}$ , a run time tool for detecting and predicting $\mathcal{PR}\mathrm{ivacy}\ \mathrm{vi}\mathcal{O}\mathrm{la}\mathcal{T}\mathrm{ions}\ \mathrm{in}\ \mathcal{O}\mathrm{nline}\ \mathcal{S}\mathrm{ocial}\ \mathrm{network}\mathcal{S}$ . $\mathcal{PROTOSS}$ captures relations among users, their privacy agreements with an online social network operator, as well as domain-based semantic information and rules. It uses model checking to detect if relations among the users will result in the violation of privacy agreements. It can further use the semantic information to infer possible violations that have not been specified by the user explicitly. In addition to detection, $\mathcal{PROTOSS}$ can predict possible future violations by feeding in a hypothetical future world state. Through a running example, we show that $\mathcal{PROTOSS}$ can detect and predict subtle leakages, similar to the ones reported in real life examples. We study the performance of our system on the scenario as well as on an existing Facebook dataset.     

Collaborative filtering with information-rich and information-sparse entities

In this paper, we consider a popular model for collaborative filtering in recommender systems. In particular, we consider both the clustering model, where only users (or items) are clustered, and the co-clustering model, where both users and items are clustered, and further, we assume that some users rate many items (information-rich users) and some users rate only a few items (information-sparse users). When users (or items) are clustered, our algorithm can recover the rating matrix with \(\omega (MK \log M)\) noisy entries while \(MK\) entries are necessary, where \(K\) is the number of clusters and \(M\) is the number of items. In the case of co-clustering, we prove that \(K^2\) entries are necessary for recovering the rating matrix, and our algorithm achieves this lower bound within a logarithmic factor when \(K\) is sufficiently large. Extensive simulations on Netflix and MovieLens data show that our algorithm outperforms the alternating minimization and the popularity-among-friends algorithm. The performance difference increases even more when noise is added to the datasets.     

Multi-agent based middleware for protecting privacy in IPTV content recommender services

This work presents our efforts to design an agent based middleware that enables the end-users to use IPTV content recommender services without revealing their sensitive preference data to the service provider or any third party involved in this process. The proposed middleware (called AMPR) preserves users’ privacy when using the recommender service and permits private sharing of data among different users in the network. The proposed solution relies on a distributed multi-agent architecture involving local agents running on the end-user set up box to implement a two stage concealment process based on user role in order to conceal the local preference data of end-users when they decide to participate in recommendation process. Moreover, AMPR allows the end-users to use P3P policies exchange language (APPEL) for specifying their privacy preferences for the data extracted from their profiles, while the recommender service uses platform for privacy preferences (P3P) policies for specifying their data usage practices. AMPR executes the first stage locally at the end user side but the second stage is done at remote nodes that can be donated by multiple non-colluding end users that we will call super-peers Elmisery and Botvich (2011a, b, c); or third parties mash-up service Elmisery A, Botvich (2011a, b). Participants submit their locally obfuscated profiles anonymously to their local super-peer who collect and mix these preference data from multiple participants. The super-peer invokes AMPR to perform global perturbation process on the aggregated preference data to ensure a complete concealment of user’s profiles. Then, it anonymously submits these aggregated profiles to a third party content recommender service to generate referrals without breaching participants’ privacy. In this paper, we also provide an IPTV network scenario and experimentation results. Our results and analysis shows that our two-stage concealment process not only protect the users’ privacy, but also can maintain the recommendation accuracy     

Ensuring location diversity in privacy-preserving spatio-temporal data publishing

The rise of mobile technologies in the last decade has led to vast amounts of location information generated by individuals. From the knowledge discovery point of view, these data are quite valuable, but the inherent personal information in the data raises privacy concerns. There exists many algorithms in the literature to satisfy the privacy requirements of individuals, by generalizing, perturbing, and suppressing their data. Current techniques that try to ensure a level of indistinguishability between trajectories in a dataset are direct applications of \(k\) -anonymity, thus suffer from the shortcomings of \(k\) -anonymity such as the lack of diversity in sensitive regions. Moreover, these techniques fail to incorporate some common background knowledge, an adversary might have such as the underlying map, the traffic density, and the anonymization algorithm itself. We propose a new privacy metric \(p\) -confidentiality that ensures location diversity by bounding the probability of a user visiting a sensitive location with the \(p\) input parameter. We perform our probabilistic analysis based on the background knowledge of the adversary. Instead of grouping the trajectories, we anonymize the underlying map, that is, we group nodes (points of interest) to create obfuscation areas around sensitive locations. The groups are formed in such a way that the parts of trajectories entering the groups, coupled with the adversary background, do not increase the adversary’s belief in violating the \(p\) -confidentiality. We then use the map anonymization as a model to anonymize the trajectories. We prove that our algorithm is resistant to reverse-engineering attacks when the statistics required for map anonymization is publicly available. We empirically evaluate the performance of our algorithm and show that location diversity can be satisfied effectively.     

Toward structural sparsity: an explicit \ell _{2}/\ell _0 approach

As powerful tools, machine learning and data mining techniques have been widely applied in various areas. However, in many real-world applications, besides establishing accurate black box predictors, we are also interested in white box mechanisms, such as discovering predictive patterns in data that enhance our understanding of underlying physical, biological and other natural processes. For these purposes, sparse representation and its variations have been one of the focuses. More recently, structural sparsity has attracted increasing attentions. In previous research, structural sparsity was often achieved by imposing convex but non-smooth norms such as ${\ell _{2}/\ell _{1}}$ and group ${\ell _{2}/\ell _{1}}$ norms. In this paper, we present the explicit ${\ell _2/\ell _0}$ and group ${\ell _2/\ell _0}$ norm to directly approach the structural sparsity. To tackle the problem of intractable ${\ell _2/\ell _0}$ optimizations, we develop a general Lipschitz auxiliary function that leads to simple iterative algorithms. In each iteration, optimal solution is achieved for the induced subproblem and a guarantee of convergence is provided. Furthermore, the local convergent rate is also theoretically bounded. We test our optimization techniques in the multitask feature learning problem. Experimental results suggest that our approaches outperform other approaches in both synthetic and real-world data sets.     

The performance and locality tradeoff in bittorrent-like file sharing systems

In recent years, the surge of large-scale peer-to-peer (P2P) applications has brought huge amounts of P2P traffic, which has significantly changed the Internet traffic pattern and increased the traffic-relay cost at the Internet Service Providers (ISPs). To alleviate the stress on networks, methods of localized peer selection have been proposed that advocate neighbor selection within the same network (AS or ISP) to reduce the cross-ISP traffic. Nevertheless, localized peer selection may potentially lead to the downgrade of download speed at the peers, rendering a non-negligible tradeoff between the download performance and traffic localization in the P2P system. Aiming at effective peer selection strategies that achieve any desired Pareto optimum in face of the tradeoff, our contributions in this paper are three-fold: (1) We characterize the performance and locality tradeoff as a multi-objective \(b\) -matching optimization problem. In particular, we first present a generic weighted \(b\) -matching model that characterizes the tit-for-tat in BitTorrent-like peer selection. We then introduce multiple optimization objectives into the model, which effectively characterize the performance and locality tradeoff using simultaneous objectives to optimize. (2) We design fully distributed peer selection algorithms that can effectively approximate any desired Pareto optimum of the global multi-objective optimization problem, which represents a desired tradeoff point between performance and locality in the entire system. (3) Taking network dynamics into consideration, we further propose practical protocols that allow each peer to dynamically adjust its peer selection preference on download performance or traffic locality, in order to adapt to the current quality of peering connections, while guaranteeing that the desired tradeoff is still achieved over its entire download process. To support our models and protocols, we have conducted rigorous analysis, extensive simulations, and prototype experiments under various practical settings extracted from real-world traces.     

On requirement verification for evolving Statecharts specifications

Software development processes have been evolving from rigid, pre-specified, and sequential to incremental, and iterative. This evolution has been dictated by the need to accommodate evolving user requirements and reduce the delay between design decision and feedback from users. Formal verification techniques, however, have largely ignored this evolution and even when they made enormous improvements and found significant uses in practice, like in the case of model checking, they remained confined into the niches of safety-critical systems. Model checking verifies if a system’s model \(\mathcal{M}\) satisfies a set of requirements, formalized as a set of logic properties \(\Phi\) . Current model-checking approaches, however, implicitly rely on the assumption that both the complete model \(\mathcal{M}\) and the whole set of properties \(\Phi\) are fully specified when verification takes place. Very often, however, \(\mathcal{M}\) is subject to change because its development is iterative and its definition evolves through stages of incompleteness, where alternative design decisions are explored, typically to evaluate some quality trade-offs. Evolving systems specifications of this kind ask for novel verification approaches that tolerate incompleteness and support incremental analysis of alternative designs for certain functionalities. This is exactly the focus of this paper, which develops an incremental model-checking approach for evolving Statecharts. Statecharts have been chosen both because they are increasingly used in practice natively support model refinements.     

Using kernels for a video-based mouse-replacement interface

Some people cannot use their hands to control a computer mouse due to conditions such as cerebral palsy or multiple sclerosis. For these individuals, there are various mouse-replacement solutions. One approach is to enable them to control the mouse pointer using head motions captured with a web camera. One such system, the Camera Mouse, uses an optical flow approach to track a manually-selected small patch of the subject’s face, such as the nostril or the edge of the eyebrow. The optical flow tracker may lose the facial feature when the tracked image patch drifts away from the initially-selected feature or when a user makes a rapid head movement. To address the problem of feature loss, we developed and incorporated the Kernel-Subset-Tracker into the Camera Mouse. The Kernel-Subset-Tracker is an exemplar-based method that uses a training set of representative images to produce online templates for positional tracking. We designed the augmented Camera Mouse so that it can compute these templates in real time, employing kernel techniques traditionally used for classification. We propose three versions of the Kernel-Subset-Tracker, each using a different kernel, and compared their performance to the optical-flow tracker under five different experimental conditions. Our experiments with test subjects show that augmenting the Camera Mouse with the Kernel-Subset-Tracker improves communication bandwidth statistically significantly. Tracking of facial features was accurate, without feature drift, even during rapid head movements and extreme head orientations. We conclude by describing how the Camera Mouse augmented with the Kernel-Subset-Tracker enabled a stroke-victim with severe motion impairments to communicate via an on-screen keyboard.     

Fully non-interactive onion routing with forward secrecy

Onion routing is a privacy-enabling protocol that allows users to establish anonymous channels over a public network. In such a protocol, parties send their messages through $n$ anonymizing servers (called a circuit) using several layers of encryption. Several proposals for onion routing have been published in recent years, and TOR, a real-life implementation, provides an onion routing service to thousands of users over the Internet. This paper puts forward a new onion routing protocol which outperforms TOR by achieving forward secrecy in a fully non-interactive fashion, without requiring any communication from the router and/or the users and the service provider to update time-related keys. We compare this to TOR which requires $O(n^2)$ rounds of interaction to establish a circuit of size $n$ . In terms of the computational effort required to the parties, our protocol is comparable to TOR, but the network latency associated with TOR’s high round complexity ends up dominating the running time. Compared to other recently proposed alternative to TOR, such as the PB-OR (PETS 2007) and CL-OR (CCS 2009) protocols, our scheme still has the advantage of being non-interactive (both PB-OR and CL-OR require some interaction to update time-sensitive information), and achieves similar computational performances. We performed implementation and simulation tests that confirm our theoretical analysis. Additionally, while comparing our scheme to PB-OR, we discovered a flaw in the security of that scheme which we repair in this paper. Our solution is based on the application of forward secure encryption. We design a forward secure encryption scheme (of independent interest) to be used as the main encryption scheme in our onion routing protocol.     

Scalability and robustness of parallel hyperheuristics applied to a multiobjectivised frequency assignment problem

The Frequency Assignment Problem (fap) is one of the key issues in the design of Global System for Mobile Communications (gsm) networks. The formulation of the fap used here focuses on aspects that are relevant to real gsm networks. In this paper, we adapt a parallel model to tackle a multiobjectivised version of the fap. It is a hybrid model which combines an island-based model and a hyperheuristic. The main aim of this paper is to design a strategy that facilitates the application of the current best-behaved algorithm. Specifically, our goal is to decrease the user effort required to set its parameters. At the same time, the usage of such an algorithm in parallel environments was enabled. As a result, the time required to attain high-quality solutions was decreased. We also conduct a robustness analysis of this parallel model. In this analysis we study the relationship between the migration stage of the parallel model and the quality of the resulting solutions. In addition, we also carry out a scalability study of the parallel model. In this case, we analyse the impact that the migration stage has on the scalability of the entire parallel model. Computational results with several real network instances have validated our proposed approach. The best-known frequency plans for two real-world network instances are improved with this strategy.     

The Nonconvergence of h-Refinement in Prolate Elements

Prolate elements are a “plug-compatible” modification of spectral elements in which Legendre polynomials are replaced by prolate spheroidal wave functions of order zero. Prolate functions contain a“bandwidth parameter” $c \ge 0 $ c ≥ 0 whose value is crucial to numerical performance; the prolate functions reduce to Legendre polynomials for $c\,=\,0$ c = 0 . We show that the optimal bandwidth parameter $c$ c not only depends on the number of prolate modes per element $N$ N , but also on the element widths $h$ h . We prove that prolate elements lack $h$ h -convergence for fixed $c$ c in the sense that the error does not go to zero as the element size $h$ h is made smaller and smaller. Furthermore, the theoretical predictions that Chebyshev and Legendre polynomials require $\pi $ π degrees of freedom per wavelength to resolve sinusoidal functions while prolate series need only 2 degrees of freedom per wavelength are asymptotic limits as $N \rightarrow \infty $ N → ∞ ; we investigate the rather different behavior when $N \sim O(4-10)$ N ～ O ( 4 ? 10 ) as appropriate for spectral elements and prolate elements. On the other hand, our investigations show that there are certain combinations of $N,\,h$ N , h and $c>0$ c > 0 where a prolate basis clearly outperforms the Legendre polynomial approximation.     

The Minimum Vulnerability Problem

We revisit the problem of finding \(k\) paths with a minimum number of shared edges between two vertices of a graph. An edge is called shared if it is used in more than one of the \(k\) paths. We provide a \({\lfloor {k/2}\rfloor }\) -approximation algorithm for this problem, improving the best previous approximation factor of \(k-1\) . We also provide the first approximation algorithm for the problem with a sublinear approximation factor of \(O(n^{3/4})\) , where \(n\) is the number of vertices in the input graph. For sparse graphs, such as bounded-degree and planar graphs, we show that the approximation factor of our algorithm can be improved to \(O(\sqrt{n})\) . While the problem is NP-hard, and even hard to approximate to within an \(O(\log n)\) factor, we show that the problem is polynomially solvable when \(k\) is a constant. This settles an open problem posed by Omran et al. regarding the complexity of the problem for small values of \(k\) . We present most of our results in a more general form where each edge of the graph has a sharing cost and a sharing capacity, and there is a vulnerability parameter \(r\) that determines the number of times an edge can be used among different paths before it is counted as a shared/vulnerable edge.     

Structuring unreliable radio networks

In this paper we study the problem of building a constant-degree connected dominating set (CCDS), a network structure that can be used as a communication backbone, in the dual graph radio network model (Clementi et al. in J Parallel Distrib Comput 64:89–96, 2004; Kuhn et al. in Proceedings of the international symposium on principles of distributed computing 2009, Distrib Comput 24(3–4):187–206 2011, Proceedings of the international symposium on principles of distributed computing 2010). This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. Real networks compensate for this differing quality by deploying low-layer detection protocols to filter unreliable from reliable links. With this in mind, we begin by presenting an algorithm that solves the CCDS problem in the dual graph model under the assumption that every process $u$ is provided with a local link detector set consisting of every neighbor connected to $u$ by a reliable link. The algorithm solves the CCDS problem in $O\left( \frac{\varDelta \log ^2{n}}{b} + \log ^3{n}\right) $ rounds, with high probability, where $\varDelta $ is the maximum degree in the reliable link graph, $n$ is the network size, and $b$ is an upper bound in bits on the message size. The algorithm works by first building a Maximal Independent Set (MIS) in $\log ^3{n}$ time, and then leveraging the local topology knowledge to efficiently connect nearby MIS processes. A natural follow-up question is whether the link detector must be perfectly reliable to solve the CCDS problem. With this in mind, we first describe an algorithm that builds a CCDS in $O(\varDelta $ polylog $(n))$ time under the assumption of $O(1)$ unreliable links included in each link detector set. We then prove this algorithm to be (almost) tight by showing that the possible inclusion of only a single unreliable link in each process’s local link detector set is sufficient to require $\varOmega (\varDelta )$ rounds to solve the CCDS problem, regardless of message size. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time.     

Query reverse engineering

In this paper, we introduce a new problem termed query reverse engineering (QRE). Given a database \(D\) and a result table \(T\) —the output of some known or unknown query \(Q\) on \(D\) —the goal of QRE is to reverse-engineer a query \(Q'\) such that the output of query \(Q'\) on database \(D\) (denoted by \(Q'(D)\) ) is equal to \(T\) (i.e., \(Q(D)\) ). The QRE problem has useful applications in database usability, data analysis, and data security. In this work, we propose a data-driven approach, TALOS for Tree-based classifier with At Least One Semantics, that is based on a novel dynamic data classification formulation and extend the approach to efficiently support the three key dimensions of the QRE problem: whether the input query is known/unknown, supporting different query fragments, and supporting multiple database versions.     

Frequency capping in online advertising

We study the following online problem. There are n advertisers. Each advertiser \(a_i\) has a total demand \(d_i\) and a value \(v_i\) for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated with a user, and each advertiser \(a_i\) is willing to accept no more than \(f_i\) units associated with any single user (the value \(f_i\) is called the frequency cap of advertiser \(a_i\) ). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic \(3/4\) -competitiveness upper bound, which holds even when all frequency caps are \(1\) , and all advertisers share identical values and demands. A competitive ratio approaching \(1-1/e\) can be achieved via a reduction to a different model considered by Goel and Mehta (WINE ‘07: Workshop on Internet and Network, Economics: 335–340, 2007). Our main contribution is analyzing two \(3/4\) -competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal integral demand to frequency cap ratios. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the ratio of \(1-1/e\) .