OpenRaiser/Intern-Atlas huggingface dataset:
Detecting Cohesive and 2-mode Communities in Directed and Undirected Networks
Venue: arXiv cs.SI 2014
Year: 2014

Networks are a general language for representing relational information among objects. An effective way to model, reason about, and summarize networks, is to discover sets of nodes with common connectivity patterns. Such sets are commonly referred to as network communities. Research on network community detection has predominantly focused on identifying communities of densely connected nodes in undirected networks. In this paper we develop a novel overlapping community detection method that scales to networks of millions of nodes and edges and advances research along two dimensions: the connectivity structure of communities, and the use of edge directedness for community detection. First, we extend traditional definitions of network communities by building on the observation that nodes can be densely interlinked in two different ways: In cohesive communities nodes link to each other, while in 2-mode communities nodes link in a bipartite fashion, where links predominate between the two partitions rather than inside them. Our method successfully detects both 2-mode as well as cohesive communities, that may also overlap or be hierarchically nested. Second, while most existing community detection methods treat directed edges as though they were undirected, our method accounts for edge directions and is able to identify novel and meaningful community structures in both directed and undirected networks, using data from social, biological, and ecological domains.
Bounding Embeddings of VC Classes into Maximum Classes
Venue: arXiv cs.LG 2014
Year: 2014

One of the earliest conjectures in computational learning theory-the Sample Compression conjecture-asserts that concept classes (equivalently set systems) admit compression schemes of size linear in their VC dimension. To-date this statement is known to be true for maximum classes---those that possess maximum cardinality for their VC dimension. The most promising approach to positively resolving the conjecture is by embedding general VC classes into maximum classes without super-linear increase to their VC dimensions, as such embeddings would extend the known compression schemes to all VC classes. We show that maximum classes can be characterised by a local-connectivity property of the graph obtained by viewing the class as a cubical complex. This geometric characterisation of maximum VC classes is applied to prove a negative embedding result which demonstrates VC-d classes that cannot be embedded in any maximum class of VC dimension lower than 2d. On the other hand, we show that every VC-d class C embeds in a VC-(d+D) maximum class where D is the deficiency of C, i.e., the difference between the cardinalities of a maximum VC-d class and of C. For VC-2 classes in binary n-cubes for 4 <= n <= 6, we give best possible results on embedding into maximum classes. For some special classes of Boolean functions, relationships with maximum classes are investigated. Finally we give a general recursive procedure for embedding VC-d classes into VC-(d+k) maximum classes for smallest k.
On Index Coding in Noisy Broadcast Channels with Receiver Message Side Information
Venue: arXiv cs.IT 2014
Year: 2014

This letter investigates the role of index coding in the capacity of AWGN broadcast channels with receiver message side information. We first show that index coding is unnecessary where there are two receivers; multiplexing coding and superposition coding are sufficient to achieve the capacity region. We next show that, for more than two receivers, multiplexing coding and superposition coding alone can be suboptimal. We give an example where these two coding schemes alone cannot achieve the capacity region, but adding index coding can. This demonstrates that, in contrast to the two-receiver case, multiplexing coding cannot fulfill the function of index coding where there are three or more receivers.
Polynomials vanishing on grids: The Elekes-Rónyai problem revisited
Venue: arXiv cs.CG 2014
Year: 2014

In this paper we characterize real bivariate polynomials which have a small range over large Cartesian products. We show that for every constant-degree bivariate real polynomial $f$, either $|f(A,B)|=Ω(n^{4/3})$, for every pair of finite sets $A,B\subset{\mathbb R}$, with $|A|=|B|=n$ (where the constant of proportionality depends on ${\rm deg} f$), or else $f$ must be of one of the special forms $f(u,v)=h(φ(u)+ψ(v))$, or $f(u,v)=h(φ(u)\cdotψ(v))$, for some univariate polynomials $φ,ψ,h$ over ${\mathbb R}$. This significantly improves a result of Elekes and Rónyai (2000). Our results are cast in a more general form, in which we give an upper bound for the number of zeros of $z=f(x,y)$ on a triple Cartesian product $A\times B\times C$, when the sizes $|A|$, $|B|$, $|C|$ need not be the same; the upper bound is $O(n^{11/6})$ when $|A|=|B|=|C|=n$, where the constant of proportionality depends on ${\rm deg} f$, unless $f$ has one of the aforementioned special forms. This result provides a unified tool for improving bounds in various Erd\H os-type problems in geometry and additive combinatorics. Several applications of our results to problems of these kinds are presented. For example, we show that the number of distinct distances between $n$ points lying on a constant-degree parametric algebraic curve which does not contain a line, in any dimension, is $Ω(n^{4/3})$, extending the result of Pach and de Zeeuw (2013) and improving the bound of Charalambides (2012), for the special case where the curve under consideration has a polynomial parameterization. We also derive improved lower bounds for several variants of the sum-product problem in additive combinatorics.
Mobile Services and ICT4D, To the Network Economy - Bridging the Digital Divide, Ethiopia's Case
Venue: arXiv cs.CY 2014
Year: 2014

This paper presents a development paradigm for Ethiopia, based on appropriate services and innovative use of mobile communications technologies via applications tailored for sectors like business, finance, healthcare, governance, education and infotainment. The experience of other developing countries like India and Kenya is cited so as to adapt those to the Ethiopian context. Notable application areas in the aforementioned sectors have been outlined. The ETC 'next generation network' is taken into consideration, with an emphasis on mobile service offering by the Telco itself and/or third party service providers. In addition, enabling technologies like mobile internet, location-based systems, open interfaces to large telecom networks, specifically service-oriented architecture (SOA), Parlay/JAIN and the like are discussed. The paper points out possible endeavors by such stakeholders like: telecom agencies and network operators; businesses, government and NGOs; entrepreneurs and innovators; technology companies and professionals; as well as researchers and academic institutions. ICT4D through mobile services and their role in bridging the digital divide by building a virtual 'network economy' is presented.
Conceptual Framework for Internet of Things' Virtualization via OpenFlow in Context-aware Networks
Venue: arXiv cs.NI 2014
Year: 2014

A novel conceptual framework is presented in this paper with an aim to standardize and virtualize Internet of Things(IoT) infrastructure through deploying OpenFlow technology. The framework can receivee services based on context information leaving the current infrastructure unchanged. This framework allows the active collaboration of heterogeneous devices and protocols. Moreover it is capable to model placement of physical objects, manage the system and to collect information for services deployed on an IoT infrastructure. Our proposed IoT virtualization is applicable to a random topology scenario which makes it possible to 1) share flow sensors resources 2) establish multioperational sensor networks, and 3) extend reachability within the framework without establishing any further physical networks. Flow sensors achieve better results comparable to the typical sensors with respect to packet generation, reachability, simulation time, throughput, energy consumption point of view. Even better results are possible through utilizing multicast groups in large scale networks.
Securing Smartphones: A Micro-TCB Approach
Venue: arXiv cs.CR 2014
Year: 2014

As mobile phones have evolved into `smartphones', with complex operating systems running third- party software, they have become increasingly vulnerable to malicious applications (malware). We introduce a new design for mitigating malware attacks against smartphone users, based on a small trusted computing base module, denoted uTCB. The uTCB manages sensitive data and sensors, and provides core services to applications, independently of the operating system. The user invokes uTCB using a simple secure attention key, which is pressed in order to validate physical possession of the device and authorize a sensitive action; this protects private information even if the device is infected with malware. We present a proof-of-concept implementation of uTCB based on ARM's TrustZone, a secure execution environment increasingly found in smartphones, and evaluate our implementation using simulations.
Lectures on DNA Codes
Venue: arXiv cs.IT 2014
Year: 2014

For $q$-ary $n$-sequences, we develop the concept of similarity functions that can be used (for $q=4$) to model a thermodynamic similarity on DNA sequences. A similarity function is identified by the length of a longest common subsequence between two $q$-ary $n$-sequences. Codes based on similarity functions are called DNA codes. DNA codes are important components in biomolecular computing and other biotechnical applications that employ DNA hybridization assays. The main aim of the given lecture notes -- to discuss lower bounds on the rate of optimal DNA codes for a biologically motivated similarity function called a block similarity and for the conventional deletion similarity function used in the theory of error-correcting codes. We also present constructions of suboptimal DNA codes based on the parity-check code detecting one error in the Hamming metric.
Comparing the Performance of Different x86 SIMD Instruction Sets for a Medical Imaging Application on Modern Multi- and Manycore Chips
Venue: arXiv cs.DC 2014
Year: 2014

Single Instruction, Multiple Data (SIMD) vectorization is a major driver of performance in current architectures, and is mandatory for achieving good performance with codes that are limited by instruction throughput. We investigate the efficiency of different SIMD-vectorized implementations of the RabbitCT benchmark. RabbitCT performs 3D image reconstruction by back projection, a vital operation in computed tomography applications. The underlying algorithm is a challenge for vectorization because it consists, apart from a streaming part, also of a bilinear interpolation requiring scattered access to image data. We analyze the performance of SSE (128 bit), AVX (256 bit), AVX2 (256 bit), and IMCI (512 bit) implementations on recent Intel x86 systems. A special emphasis is put on the vector gather implementation on Intel Haswell and Knights Corner microarchitectures. Finally we discuss why GPU implementations perform much better for this specific algorithm.
Lectures on Designing Screening Experiments
Venue: arXiv cs.IT 2014
Year: 2014

Designing Screening Experiments (DSE) is a class of information - theoretical models for multiple - access channels (MAC). We discuss the combinatorial model of DSE called a disjunct channel model. This model is the most important for applications and closely connected with the superimposed code concept. We give a detailed survey of lower and upper bounds on the rate of superimposed codes. The best known constructions of superimposed codes are considered in paper. We also discuss the development of these codes (non-adaptive pooling designs) intended for the clone - library screening problem. We obtain lower and upper bounds on the rate of binary codes for the combinatorial model of DSE called an adder channel model. We also consider the concept of universal decoding for the probabilistic DSE model called a symmetric model of DSE.
Bayesian Pursuit Algorithms
Venue: arXiv cs.IT 2014
Year: 2014

This paper addresses the sparse representation (SR) problem within a general Bayesian framework. We show that the Lagrangian formulation of the standard SR problem, i.e., $\mathbf{x}^\star=\arg\min_\mathbf{x} \lbrace \| \mathbf{y}-\mathbf{D}\mathbf{x} \|_2^2+λ\| \mathbf{x}\|_0 \rbrace$, can be regarded as a limit case of a general maximum a posteriori (MAP) problem involving Bernoulli-Gaussian variables. We then propose different tractable implementations of this MAP problem that we refer to as "Bayesian pursuit algorithms". The Bayesian algorithms are shown to have strong connections with several well-known pursuit algorithms of the literature (e.g., MP, OMP, StOMP, CoSaMP, SP) and generalize them in several respects. In particular, i) they allow for atom deselection; ii) they can include any prior information about the probability of occurrence of each atom within the selection process; iii) they can encompass the estimation of unkown model parameters into their recursions.
A Faster Parameterized Algorithm for Treedepth
Venue: arXiv cs.DS 2014
Year: 2014

The width measure \emph{treedepth}, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which---given as input an $n$-vertex graph, a tree decomposition of the graph of width $w$, and an integer $t$---decides Treedepth, i.e. whether the treedepth of the graph is at most $t$, in time $2^{O(wt)} \cdot n$. If necessary, a witness structure for the treedepth can be constructed in the same running time. In conjunction with previous results we provide a simple algorithm and a fast algorithm which decide treedepth in time $2^{2^{O(t)}} \cdot n$ and $2^{O(t^2)} \cdot n$, respectively, which do not require a tree decomposition as part of their input. The former answers an open question posed by Ossona de Mendez and Nesetril as to whether deciding Treedepth admits an algorithm with a linear running time (for every fixed $t$) that does not rely on Courcelle's Theorem or other heavy machinery. For chordal graphs we can prove a running time of $2^{O(t \log t)}\cdot n$ for the same algorithm.
Slope Instability of the Earthen Levee in Boston, UK: Numerical Simulation and Sensor Data Analysis
Venue: arXiv cs.CE 2014
Year: 2014

The paper presents a slope stability analysis for a heterogeneous earthen levee in Boston, UK, which is prone to occasional slope failures under tidal loads. Dynamic behavior of the levee under tidal fluctuations was simulated using a finite element model of variably saturated linear elastic perfectly plastic soil. Hydraulic conductivities of the soil strata have been calibrated according to piezometers readings, in order to obtain correct range of hydraulic loads in tidal mode. Finite element simulation was complemented with series of limit equilibrium analyses. Stability analyses have shown that slope failure occurs with the development of a circular slip surface located in the soft clay layer. Both models (FEM and LEM) confirm that the least stable hydraulic condition is the combination of the minimum river levels at low tide with the maximal saturation of soil layers. FEM results indicate that in winter time the levee is almost at its limit state, at the margin of safety (strength reduction factor values are 1.03 and 1.04 for the low-tide and high-tide phases, respectively); these results agree with real-life observations. The stability analyses have been implemented as real-time components integrated into the UrbanFlood early warning system for flood protection.
Security Implications of Distributed Database Management System Models
Venue: arXiv cs.DB 2014
Year: 2014

Security features must be addressed when escalating a distributed database. The choice between the object oriented and the relational data model, several factors should be considered. The most important of these factors are single and multilevel access controls (MAC), protection and integrity maintenance. While determining which distributed database replica will be more secure for a particular function, the choice should not be made exclusively on the basis of available security features. One should also query the effectiveness and efficiency of the delivery of these characteristics. In this paper, the security strengths and weaknesses of both database models and the thorough problems initiate in the distributed environment are conversed.
A Maintainability Checklist for Spreadsheets
Venue: arXiv cs.SE 2014
Year: 2014

Spreadsheets are widely used in industry, because they are flexible and easy to use. Often, they are even used for business-critical applications. It is however difficult for spreadsheet users to correctly assess the maintainability of spreadsheets. Maintainability of spreadsheets is important, since spreadsheets often have a long lifespan, during which they are used by several users. In this paper, we present a checklist aimed at measuring the maintainability of a spreadsheet. This is achieved via asking several questions, and can indicate whether the spreadsheet is safe to use now and in the future. We demonstrate the applicability of our approach on 11 spreadsheets from the EUSES corpus.
Codes over a subset of Octonion Integers
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we define codes over some Octonion integers. We prove that in some conditions these codes can correct up to two errors for a transmitted vector and the code rate of the codes is grater than the code rate of the codes defined on some subset of Quaternion integers.
Balancing lists: a proof pearl
Venue: arXiv cs.DS 2014
Year: 2014

Starting with an algorithm to turn lists into full trees which uses non-obvious invariants and partial functions, we progressively encode the invariants in the types of the data, removing most of the burden of a correctness proof. The invariants are encoded using non-uniform inductive types which parallel numerical representations in a style advertised by Okasaki, and a small amount of dependent types.
Transit Fare Arbitrage: Case Study of San Francisco Bay Area Rapid Transit (BART) System
Venue: arXiv cs.CY 2014
Year: 2014

Transit fare arbitrage is the scenario when two or more commuters agree to swap tickets during travel in such a way that total cost is lower than otherwise. Such arbitrage allows pricing inefficiencies to be explored and exploited, leading to improved pricing models. In this paper we discuss the basics of fare arbitrage through an intuitive pricing framework involving population density. We then analyze the San Francisco Bay Area Rapid Transit (BART) system to understand underlying inefficiencies. We also provide source code and comprehensive list of pairs of trips with significant arbitrage gain at github.com/asifhaque/transit-arbitrage. Finally, we point towards a uniform payment interface for different kinds of transit systems.
Defect Detection Efficiency A Combined Approach
Venue: arXiv cs.SE 2014
Year: 2014

Survival of IT industries depends much upon the development of high quality and customer satisfied software products. Quality however can be viewed from various perspectives such as deployment of the products within estimated resources, constrains and also being defect free. Testing is one of the promising techniques ever since the inception of software in the global market. Though there are several testing techniques existing, the most widely accepted is the conventional scripted testing. Despite of advancement in the technology, achieving defect free deliverables is yet a challenge. This paper therefore aims to enhance the existing testing techniques in order to achieve nearly zero defect products through the combined approach of scripted and exploratory testing. This approach thus enables the testing team to capture maximum defects and thereby reduce the expensive nature of overheads. Further, it leads towards generation of high quality products and assures the continued customer satisfaction.
Scoping Software Process Models - Initial Concepts and Experience from Defining Space Standards
Venue: arXiv cs.SE 2014
Year: 2014

Defining process standards by integrating, harmonizing, and standardizing heterogeneous and often implicit processes is an important task, especially for large development organizations. However, many challenges exist, such as limiting the scope of process standards, coping with different levels of process model abstraction, and identifying relevant process variabilities to be included in the standard. On the one hand, eliminating process variability by building more abstract models with higher degrees of interpretation has many disadvantages, such as less control over the process. Integrating all kinds of variability, on the other hand, leads to high process deployment costs. This article describes requirements and concepts for determining the scope of process standards based on a characterization of the potential products to be produced in the future, the projects expected for the future, and the respective process capabilities needed. In addition, the article sketches experience from determining the scope of space process standards for satellite software development. Finally, related work with respect to process model scoping, conclusions, and an outlook on future work are presented.
Failure Detection and Recovery in Hierarchical Network Using FTN Approach
Venue: arXiv cs.DC 2014
Year: 2014

In current scenario several commercial and social organizations are using computer networks for their business and management purposes. In order to meet the business requirements networks are also grow. The growth of network also promotes the handling capability of large networks because it counter raises the possibilities of various faults in the network. A fault in network degrades its performance by affecting parameters like throughput, delay, latency, reliability etc. In hierarchical network models any possibility of fault may collapse entire network. If a fault occurrence disables a device in hierarchical network then it may distresses all the devices underneath. Thus it affects entire networks performance. In this paper we propose Fault Tolerable hierarchical Network (FTN) approach as a solution to the problems of hierarchical networks. The proposed approach firstly detects possibilities of fault in the network and accordingly provides specific recovery mechanism. We have evaluated the performance of FTN approach in terms of delay and throughput of network.
Cooperative Product Games
Venue: arXiv cs.GT 2014
Year: 2014

I introduce cooperative product games (CPGs), a cooperative game where every player has a weight, and the value of a coalition is the product of the weights of the players in the coalition. I only look at games where the weights are at least $2$. I show that no player in such a game can be a dummy. I show that the game is convex, and therefore always has a non-empty core. I provide a simple method for finding a payoff vector in the core.
Sensing for Spectrum Sharing in Cognitive LTE-A Cellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

In this work we present a case for dynamic spectrum sharing between different operators in systems with carrier aggregation (CA) which is an important feature in 3GPP LTE-A systems. Cross-carrier scheduling and sensing are identified as key enablers for such spectrum sharing in LTE-A. Sensing is classified as Type 1 sensing and Type 2 sensing and the role of each in the system operation is discussed. The more challenging Type 2 sensing which involves sensing the interfering signal in the presence of a desired signal is studied for a single-input single-output system. Energy detection and the most powerful test are formulated. The probability of false alarm and of detection are analyzed for energy detectors. Performance evaluations show that reasonable sensing performance can be achieved with the use of channel state information, making such sensing practically viable.