OpenRaiser/Intern-Atlas huggingface dataset:
Social Resilience in Online Communities: The Autopsy of Friendster
Venue: arXiv cs.SI 2013
Year: 2013

We empirically analyze five online communities: Friendster, Livejournal, Facebook, Orkut, Myspace, to identify causes for the decline of social networks. We define social resilience as the ability of a community to withstand changes. We do not argue about the cause of such changes, but concentrate on their impact. Changes may cause users to leave, which may trigger further leaves of others who lost connection to their friends. This may lead to cascades of users leaving. A social network is said to be resilient if the size of such cascades can be limited. To quantify resilience, we use the k-core analysis, to identify subsets of the network in which all users have at least k friends. These connections generate benefits (b) for each user, which have to outweigh the costs (c) of being a member of the network. If this difference is not positive, users leave. After all cascades, the remaining network is the k-core of the original network determined by the cost-to-benefit c/b ratio. By analysing the cumulative distribution of k-cores we are able to calculate the number of users remaining in each community. This allows us to infer the impact of the c/b ratio on the resilience of these online communities. We find that the different online communities have different k-core distributions. Consequently, similar changes in the c/b ratio have a different impact on the amount of active users. As a case study, we focus on the evolution of Friendster. We identify time periods when new users entering the network observed an insufficient c/b ratio. This measure can be seen as a precursor of the later collapse of the community. Our analysis can be applied to estimate the impact of changes in the user interface, which may temporarily increase the c/b ratio, thus posing a threat for the community to shrink, or even to collapse.
Mitigating Timing Side Channel in Shared Schedulers
Venue: arXiv cs.CR 2013
Year: 2013

In this work, we study information leakage in timing side channels that arise in the context of shared event schedulers. Consider two processes, one of them an innocuous process (referred to as Alice) and the other a malicious one (referred to as Bob), using a common scheduler to process their jobs. Based on when his jobs get processed, Bob wishes to learn about the pattern (size and timing) of jobs of Alice. Depending on the context, knowledge of this pattern could have serious implications on Alice's privacy and security. For instance, shared routers can reveal traffic patterns, shared memory access can reveal cloud usage patterns, and suchlike. We present a formal framework to study the information leakage in shared resource schedulers using the pattern estimation error as a performance metric. The first-come-first-serve (FCFS) scheduling policy and time-division-multiple-access (TDMA) are identified as two extreme policies on the privacy metric, FCFS has the least, and TDMA has the highest. However, on performance based metrics, such as throughput and delay, it is well known that FCFS significantly outperforms TDMA. We then derive two parametrized policies, accumulate and serve, and proportional TDMA, which take two different approaches to offer a tunable trade-off between privacy and performance.
Scalable Routing on Flat Names
Venue: arXiv cs.NI 2013
Year: 2013

We introduce a protocol which routes on flat, location-independent identifiers with guaranteed scalability and low stretch. Our design builds on theoretical advances in the area of compact routing, and is the first to realize these guarantees in a dynamic distributed setting.
Robust Capon Beamforming via Shaping Beam Pattern
Venue: arXiv cs.IT 2013
Year: 2013

High sidelobe level and direction of arrival (DOA) estimation sensitivity are two major disadvantages of the Capon beamforming. To deal with these problems, this paper gives an overview of a series of robust Capon beamforming methods via shaping beam pattern, including sparse Capon beamforming, weighted sparse Capon beamforming, mixed norm based Capon beamforming, total variation minimization based Capon beamforming, mainlobe-to-sidelobe power ratio maximization based Capon beamforming. With these additional structure-inducing constraints, the sidelobe is suppressed, and the robustness against DOA mismatch is improved too. Simulations show that the obtained beamformers outperform the standard Capon beamformer.
Generation of Biometric key for use in DES
Venue: arXiv cs.CR 2013
Year: 2013

Cryptography is an important field in the area of data encryption. There are different cryptographic techniques available varying from the simplest to complex. One of the complex symmetric key cryptography techniques is using Data Encryption Standard Algorithm. This paper explores a unique approach to generation of key using fingerprint. The generated key is used as an input key to the DES Algorithm
Entropy-based disciplinarity indicator: role taxonomy of journals in scientific communication systems and isolation degree. Knowledge importation/exportation profiles from journals and disciplines
Venue: arXiv cs.DL 2013
Year: 2013

In this research, a new indicator of disciplinarity-multidisciplinarity is developed, discussed and applied. EBDI is based on the combination of the frequency distribution of subject categories of journals citing or cited by the analysis unit and the spread and diversity of the citations among subject categories measured with Shannon-Wiener entropy. Its reproducibility, robustness and consistence are discussed. Four of the combinations of its values when applied to the cited and citing dimensions lead to a suggested taxonomy of the role that the studied unit might have in terms of the transformation of knowledge from different disciplines in the scientific communication system and its position respect a hypothetical thematic core of the discipline in which it has been classified. The indicator is applied to the journals belonging to the first quartile of JCR-SSCI 2011 Library and Information Science and an indicator-based taxonomy is applied and discussed, pointing to differential thematic roles of the journals analyzed.
Using Modified Partitioning Around Medoids Clustering Technique in Mobile Network Planning
Venue: arXiv cs.AI 2013
Year: 2013

Every cellular network deployment requires planning and optimization in order to provide adequate coverage, capacity, and quality of service (QoS). Optimization mobile radio network planning is a very complex task, as many aspects must be taken into account. With the rapid development in mobile network we need effective network planning tool to satisfy the need of customers. However, deciding upon the optimum placement for the base stations (BS s) to achieve best services while reducing the cost is a complex task requiring vast computational resource. This paper introduces the spatial clustering to solve the Mobile Networking Planning problem. It addresses antenna placement problem or the cell planning problem, involves locating and configuring infrastructure for mobile networks by modified the original Partitioning Around Medoids PAM algorithm. M-PAM (Modified Partitioning Around Medoids) has been proposed to satisfy the requirements and constraints. PAM needs to specify number of clusters (k) before starting to search for the best locations of base stations. The M-PAM algorithm uses the radio network planning to determine k. We calculate for each cluster its coverage and capacity and determine if they satisfy the mobile requirements, if not we will increase (k) and reapply algorithms depending on two methods for clustering. Implementation of this algorithm to a real case study is presented. Experimental results and analysis indicate that the M-PAM algorithm when applying method two is effective in case of heavy load distribution, and leads to minimum number of base stations, which directly affected onto the cost of planning the network.
A Scalable Generative Graph Model with Community Structure
Venue: arXiv cs.SI 2013
Year: 2013

Network data is ubiquitous and growing, yet we lack realistic generative network models that can be calibrated to match real-world data. The recently proposed Block Two-Level Erdss-Renyi (BTER) model can be tuned to capture two fundamental properties: degree distribution and clustering coefficients. The latter is particularly important for reproducing graphs with community structure, such as social networks. In this paper, we compare BTER to other scalable models and show that it gives a better fit to real data. We provide a scalable implementation that requires only O(d_max) storage where d_max is the maximum number of neighbors for a single node. The generator is trivially parallelizable, and we show results for a Hadoop MapReduce implementation for a modeling a real-world web graph with over 4.6 billion edges. We propose that the BTER model can be used as a graph generator for benchmarking purposes and provide idealized degree distributions and clustering coefficient profiles that can be tuned for user specifications.
On the Construction of Radio Environment Maps for Cognitive Radio Networks
Venue: arXiv cs.NI 2013
Year: 2013

The Radio Environment Map (REM) provides an effective approach to Dynamic Spectrum Access (DSA) in Cognitive Radio Networks (CRNs). Previous results on REM construction show that there exists a tradeoff between the number of measurements (sensors) and REM accuracy. In this paper, we analyze this tradeoff and determine that the REM error is a decreasing and convex function of the number of measurements (sensors). The concept of geographic entropy is introduced to quantify this relationship. And the influence of sensor deployment on REM accuracy is examined using information theory techniques. The results obtained in this paper are applicable not only for the REM, but also for wireless sensor network deployment.
Refine Predictions Ad Infinitum?
Venue: arXiv cs.GT 2013
Year: 2013

We study how standard auction objectives in sponsored search markets change with refinements in the prediction of the relevance (click-through rates) of ads. We study mechanisms that optimize for a convex combination of efficiency and revenue. We show that the objective function of such a mechanism can only improve with refined (improved) relevance predictions, i.e., the search engine has no disincentive to perform these refinements. More interestingly, we show that under assumptions, refinements to relevance predictions can only improve the efficiency of any such mechanism. Our main technical contribution is to study how relevance refinements affect the similarity between ranking by virtual-value (revenue ranking) and ranking by value (efficiency ranking). Finally, we discuss implications of our results to the literature on signaling.
Total communicability as a centrality measure
Venue: arXiv cs.SI 2013
Year: 2013

We examine a node centrality measure based on the notion of total communicability, defined in terms of the row sums of the exponential of the adjacency matrix of the network. We argue that this is a natural metric for ranking nodes in a network, and we point out that it can be computed very rapidly even in the case of large networks. Furthermore, we propose the total sum of node communicabilities as a useful measure of network connectivity. Extensive numerical studies are conducted in order to compare this centrality measure with the closely related ones of subgraph centrality [E. Estrada and J. A. Rodriguez-Velazquez, Phys. Rev. E, 71 (2005), 056103] and Katz centrality [L. Katz, Psychometrica, 18 (1953), pp. 39-43]. Both synthetic and real-world networks are used in the computations.
A Bayesian Method Reexamined
Venue: arXiv cs.AI 2013
Year: 2013

This paper examines the "K2" network scoring metric of Cooper and Herskovits. It shows counterintuitive results from applying this metric to simple networks. One family of noninformative priors is suggested for assigning equal scores to equivalent networks.
Possibility and Necessity Functions over Non-classical Logics
Venue: arXiv cs.AI 2013
Year: 2013

We propose an integration of possibility theory into non-classical logics. We obtain many formal results that generalize the case where possibility and necessity functions are based on classical logic. We show how useful such an approach is by applying it to reasoning under uncertain and inconsistent information.
Properties of Bayesian Belief Network Learning Algorithms
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian belief network learning algorithms have three basic components: a measure of a network structure and a database, a search heuristic that chooses network structures to be considered, and a method of estimating the probability tables from the database. This paper contributes to all these three topics. The behavior of the Bayesian measure of Cooper and Herskovits and a minimum description length (MDL) measure are compared with respect to their properties for both limiting size and finite size databases. It is shown that the MDL measure has more desirable properties than the Bayesian measure when a distribution is to be learned. It is shown that selecting belief networks with certain minimallity properties is NP-hard. This result justifies the use of search heuristics instead of exact algorithms for choosing network structures to be considered. In some cases, a collection of belief networks can be represented by a single belief network which leads to a new kind of probability table estimation called smoothing. We argue that smoothing can be efficiently implemented by incorporating it in the search heuristic. Experimental results suggest that for learning probabilities of belief networks smoothing is helpful.
Efficient Estimation of the Value of Information in Monte Carlo Models
Venue: arXiv cs.AI 2013
Year: 2013

The expected value of information (EVI) is the most powerful measure of sensitivity to uncertainty in a decision model: it measures the potential of information to improve the decision, and hence measures the expected value of outcome. Standard methods for computing EVI use discrete variables and are computationally intractable for models that contain more than a few variables. Monte Carlo simulation provides the basis for more tractable evaluation of large predictive models with continuous and discrete variables, but so far computation of EVI in a Monte Carlo setting also has appeared impractical. We introduce an approximate approach based on pre-posterior analysis for estimating EVI in Monte Carlo models. Our method uses a linear approximation to the value function and multiple linear regression to estimate the linear model from the samples. The approach is efficient and practical for extremely large models. It allows easy estimation of EVI for perfect or partial information on individual variables or on combinations of variables. We illustrate its implementation within Demos (a decision modeling system), and its application to a large model for crisis transportation planning.
A Probabilistic Model of Action for Least-Commitment Planning with Information Gather
Venue: arXiv cs.AI 2013
Year: 2013

AI planning algorithms have addressed the problem of generating sequences of operators that achieve some input goal, usually assuming that the planning agent has perfect control over and information about the world. Relaxing these assumptions requires an extension to the action representation that allows reasoning both about the changes an action makes and the information it provides. This paper presents an action representation that extends the deterministic STRIPS model, allowing actions to have both causal and informational effects, both of which can be context dependent and noisy. We also demonstrate how a standard least-commitment planning algorithm can be extended to include informational actions and contingent execution.
Value of Evidence on Influence Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we introduce evidence propagation operations on influence diagrams and a concept of value of evidence, which measures the value of experimentation. Evidence propagation operations are critical for the computation of the value of evidence, general update and inference operations in normative expert systems which are based on the influence diagram (generalized Bayesian network) paradigm. The value of evidence allows us to compute directly an outcome sensitivity, a value of perfect information and a value of control which are used in decision analysis (the science of decision making under uncertainty). More specifically, the outcome sensitivity is the maximum difference among the values of evidence, the value of perfect information is the expected value of the values of evidence, and the value of control is the optimal value of the values of evidence. We also discuss an implementation and a relative computational efficiency issues related to the value of evidence and the value of perfect information.
Backward Simulation in Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

Backward simulation is an approximate inference technique for Bayesian belief networks. It differs from existing simulation methods in that it starts simulation from the known evidence and works backward (i.e., contrary to the direction of the arcs). The technique's focus on the evidence leads to improved convergence in situations where the posterior beliefs are dominated by the evidence rather than by the prior probabilities. Since this class of situations is large, the technique may make practical the application of approximate inference in Bayesian belief networks to many real-world problems.
An Experimental Comparison of Numerical and Qualitative Probabilistic Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Qualitative and infinitesimal probability schemes are consistent with the axioms of probability theory, but avoid the need for precise numerical probabilities. Using qualitative probabilities could substantially reduce the effort for knowledge engineering and improve the robustness of results. We examine experimentally how well infinitesimal probabilities (the kappa-calculus of Goldszmidt and Pearl) perform a diagnostic task - troubleshooting a car that will not start by comparison with a conventional numerical belief network. We found the infinitesimal scheme to be as good as the numerical scheme in identifying the true fault. The performance of the infinitesimal scheme worsens significantly for prior fault probabilities greater than 0.03. These results suggest that infinitesimal probability methods may be of substantial practical value for machine diagnosis with small prior fault probabilities.
Fuzzy Geometric Relations to Represent Hierarchical Spatial Information
Venue: arXiv cs.AI 2013
Year: 2013

A model to represent spatial information is presented in this paper. It is based on fuzzy constraints represented as fuzzy geometric relations that can be hierarchically structured. The concept of spatial template is introduced to capture the idea of interrelated objects in two-dimensional space. The representation model is used to specify imprecise or vague information consisting in relative locations and orientations of template objects. It is shown in this paper how a template represented by this model can be matched against a crisp situation to recognize a particular instance of this template. Furthermore, the proximity measure (fuzzy measure) between the instance and the template is worked out - this measure can be interpreted as a degree of similarity. In this context, template recognition can be viewed as a case of fuzzy pattern recognition. The results of this work have been implemented and applied to a complex military problem from which this work originated.
Model-Based Diagnosis with Qualitative Temporal Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we describe a framework for model-based diagnosis of dynamic systems, which extends previous work in this field by using and expressing temporal uncertainty in the form of qualitative interval relations a la Allen. Based on a logical framework extended by qualitative and quantitative temporal constraints we show how to describe behavioral models (both consistency- and abductive-based), discuss how to use abstract observations and show how abstract temporal diagnoses are computed. This yields an expressive framework, which allows the representation of complex temporal behavior allowing us to represent temporal uncertainty. Due to its abstraction capabilities computation is made independent of the number of observations and time points in a temporal setting. An example of hepatitis diagnosis is used throughout the paper.
Models of Consensus for Multiple Agent Systems
Venue: arXiv cs.MA 2013
Year: 2013

Models of consensus are used to manage multiple agent systems in order to choose between different recommendations provided by the system. It is assumed that there is a central agent that solicits recommendations or plans from other agents. That agent the n determines the consensus of the other agents, and chooses the resultant consensus recommendation or plan. Voting schemes such as this have been used in a variety of domains, including air traffic control. This paper uses an analytic model to study the use of consensus in multiple agent systems. The binomial model is used to study the probability that the consensus judgment is correct or incorrect. That basic model is extended to account for both different levels of agent competence and unequal prior odds. The analysis of that model is critical in the investigation of multiple agent systems, since the model leads us to conclude that in some cases consensus judgment is not appropriate. In addition, the results allow us to determine how many agents should be used to develop consensus decisions, which agents should be used to develop consensus decisions and under which conditions the consensus model should be used.
A Probabilistic Approach to Hierarchical Model-based Diagnosis
Venue: arXiv cs.AI 2013
Year: 2013

Model-based diagnosis reasons backwards from a functional schematic of a system to isolate faults given observations of anomalous behavior. We develop a fully probabilistic approach to model based diagnosis and extend it to support hierarchical models. Our scheme translates the functional schematic into a Bayesian network and diagnostic inference takes place in the Bayesian network. A Bayesian network diagnostic inference algorithm is modified to take advantage of the hierarchy to give computational gains.
Semigraphoids Are Two-Antecedental Approximations of Stochastic Conditional Independence Models
Venue: arXiv cs.AI 2013
Year: 2013

The semigraphoid closure of every couple of CI-statements (GI=conditional independence) is a stochastic CI-model. As a consequence of this result it is shown that every probabilistically sound inference rule for CI-model, having at most two antecedents, is derivable from the semigraphoid inference rules. This justifies the use of semigraphoids as approximations of stochastic CI-models in probabilistic reasoning. The list of all 19 potential dominant elements of the mentioned semigraphoid closure is given as a byproduct.