OpenRaiser/Intern-Atlas huggingface dataset:
Being Rational or Aggressive? A Revisit to Dunbar's Number in Online Social Networks
Venue: arXiv cs.SI 2010
Year: 2010

Recent years have witnessed the explosion of online social networks (OSNs). They provide powerful IT-innovations for online social activities such as organizing contacts, publishing contents, and sharing interests between friends who may never meet before. As more and more people become the active users of online social networks, one may ponder questions such as: (1) Do OSNs indeed improve our sociability? (2) To what extent can we expand our offline social spectrum in OSNs? (3) Can we identify some interesting user behaviors in OSNs? Our work in this paper just aims to answer these interesting questions. To this end, we pay a revisit to the well-known Dunbar's number in online social networks. Our main research contributions are as follows. First, to our best knowledge, our work is the first one that systematically validates the existence of the online Dunbar's number in the range of [200,300]. To reach this, we combine using local-structure analysis and user-interaction analysis for extensive real-world OSNs. Second, we divide OSNs users into two categories: rational and aggressive, and find that rational users intend to develop close and reciprocated relationships, whereas aggressive users have no consistent behaviors. Third, we build a simple model to capture the constraints of time and cognition that affect the evolution of online social networks. Finally, we show the potential use of our findings in viral marketing and privacy management in online social networks.
Multivariate vector sampling expansions in shift invariant subspaces
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we study multivariate vector sampling expansions on general finitely generated shift-invariant subspaces. Necessary and sufficient conditions for a multivariate vector sampling theorem to hold are given.
A New Sufficient Condition for 1-Coverage to Imply Connectivity
Venue: arXiv cs.AI 2010
Year: 2010

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully the active nodes must maintain both sensing coverage and network connectivity, It proved before if the communication range of nodes is at least twice the sensing range, complete coverage of a convex area implies connectivity among the working set of nodes. In this paper we consider a rectangular region A = a *b, such that R a R b s s £, £, where s R is the sensing range of nodes. and put a constraint on minimum allowed distance between nodes(s). according to this constraint we present a new lower bound for communication range relative to sensing range of sensors(s 2 + 3 *R) that complete coverage of considered area implies connectivity among the working set of nodes; also we present a new distribution method, that satisfy our constraint.
An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations
Venue: arXiv cs.GT 2010
Year: 2010

We show that every universally truthful randomized mechanism for combinatorial auctions with submodular valuations that provides $m^{\frac 1 2 -ε}$ approximation to the social welfare and uses value queries only must use exponentially many value queries, where $m$ is the number of items. In contrast, ignoring incentives there exist constant ratio approximation algorithms for this problem. Our approach is based on a novel \emph{direct hardness} approach and completely skips the notoriously hard characterization step. The characterization step was the main obstacle for proving impossibility results in algorithmic mechanism design so far. We demonstrate two additional applications of our new technique: (1) an impossibility result for universally-truthful polynomial time flexible combinatorial public projects and (2) an impossibility result for truthful-in-expectation mechanisms for exact combinatorial public projects. The latter is the first result that bounds the power of polynomial-time truthful in expectation mechanisms in any setting.
Degrees of Freedom Regions of Two-User MIMO Z and Full Interference Channels: The Benefit of Reconfigurable Antennas
Venue: arXiv cs.IT 2010
Year: 2010

We study the degrees of freedom (DoF) regions of two-user multiple-input multiple-output (MIMO) Z and full interference channels in this paper. We assume that the receivers always have perfect channel state information. We first derive the DoF region of Z interference channel with channel state information at transmitter (CSIT). For full interference channel without CSIT, the DoF region has been fully characterized recently and it is shown that the previously known outer bound is not achievable. In this work, we investigate the no-CSIT case further by assuming that the transmitter has the ability of antenna mode switching. We obtain the DoF region as a function of the number of available antenna modes and reveal the incremental gain in DoF that each extra antenna mode can bring. It is shown that in certain cases the reconfigurable antennas can bring extra DoF gains. In these cases, the DoF region is maximized when the number of modes is at least equal to the number of receive antennas at the corresponding receiver, in which case the previously outer bound is achieved. In all cases, we propose systematic constructions of the beamforming and nulling matrices for achieving the DoF region. The constructions bear an interesting space-frequency interpretation.
A Distributed Method for Trust-Aware Recommendation in Social Networks
Venue: arXiv cs.SI 2010
Year: 2010

This paper contains the details of a distributed trust-aware recommendation system. Trust-base recommenders have received a lot of attention recently. The main aim of trust-based recommendation is to deal the problems in traditional Collaborative Filtering recommenders. These problems include cold start users, vulnerability to attacks, etc.. Our proposed method is a distributed approach and can be easily deployed on social networks or real life networks such as sensor networks or peer to peer networks.
Forward Kinematics Analysis and Tension Distribution of a Cable-Driven Sinking Winches Mechanism
Venue: arXiv cs.CG 2010
Year: 2010

This paper concerns the forward kinematics and tension distribution of sinking winches mechanism, which is a type of four-cable-driven partly constrained parallel robot. Conventional studies on forward kinematics of cable-driven parallel robot assumed that all cables are taut. Actually, given the lengths of four cables, some cables may be slack when the platform is in static equilibrium. Therefore, in this paper, the tension state (tautness or slackness) of cables is considered in the forward kinematics model. We propose Traversal-Solving-Algorithm, which can indicate the tension state of cables, and further determine the pose of the platform, if the lengths of four cables are given. The effectiveness of the algorithm is verified by four examples. The results of this paper can be used to control sinking winches mechanism to achieve the level and stable motion of the platform, and to make the tension distribution of cables as uniform as possible.
Single Frame Image super Resolution using Learned Directionlets
Venue: arXiv cs.CV 2010
Year: 2010

In this paper, a new directionally adaptive, learning based, single image super resolution method using multiple direction wavelet transform, called Directionlets is presented. This method uses directionlets to effectively capture directional features and to extract edge information along different directions of a set of available high resolution images .This information is used as the training set for super resolving a low resolution input image and the Directionlet coefficients at finer scales of its high-resolution image are learned locally from this training set and the inverse Directionlet transform recovers the super-resolved high resolution image. The simulation results showed that the proposed approach outperforms standard interpolation techniques like Cubic spline interpolation as well as standard Wavelet-based learning, both visually and in terms of the mean squared error (mse) values. This method gives good result with aliased images also.
What is a categorical model of the differential and the resource lambda-calculi?
Venue: arXiv cs.LO 2010
Year: 2010

In this paper we provide an abstract model theory for the untyped differential lambda-calculus and the resource calculus. In particular we propose a general definition of model of these calculi, namely the notion of linear reflexive object in a Cartesian closed differential category. Examples of models based on relations are provided.
Confluence Reduction for Probabilistic Systems (extended version)
Venue: arXiv cs.LO 2010
Year: 2010

This paper presents a novel technique for state space reduction of probabilistic specifications, based on a newly developed notion of confluence for probabilistic automata. We prove that this reduction preserves branching probabilistic bisimulation and can be applied on-the-fly. To support the technique, we introduce a method for detecting confluent transitions in the context of a probabilistic process algebra with data, facilitated by an earlier defined linear format. A case study demonstrates that significant reductions can be obtained.
Distributed Storage Codes with Repair-by-Transfer and Non-achievability of Interior Points on the Storage-Bandwidth Tradeoff
Venue: arXiv cs.IT 2010
Year: 2010

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any subset of k nodes within the n-node network. However, regenerating codes possess in addition, the ability to repair a failed node by connecting to an arbitrary subset of d nodes. It has been shown that for the case of functional-repair, there is a tradeoff between the amount of data stored per node and the bandwidth required to repair a failed node. A special case of functional-repair is exact-repair where the replacement node is required to store data identical to that in the failed node. Exact-repair is of interest as it greatly simplifies system implementation. The first result of the paper is an explicit, exact-repair code for the point on the storage-bandwidth tradeoff corresponding to the minimum possible repair bandwidth, for the case when d=n-1. This code has a particularly simple graphical description and most interestingly, has the ability to carry out exact-repair through mere transfer of data and without any need to perform arithmetic operations. Hence the term `repair-by-transfer'. The second result of this paper shows that the interior points on the storage-bandwidth tradeoff cannot be achieved under exact-repair, thus pointing to the existence of a separate tradeoff under exact-repair. Specifically, we identify a set of scenarios, termed `helper node pooling', and show that it is the necessity to satisfy such scenarios that over-constrains the system.
Shape Calculus: Timed Operational Semantics and Well-formedness
Venue: arXiv cs.PL 2010
Year: 2010

The Shape Calculus is a bio-inspired calculus for describing 3D shapes moving in a space. A shape forms a 3D process when combined with a behaviour. Behaviours are specified with a timed CCS-like process algebra using a notion of channel that models naturally binding sites on the surface of shapes. Processes can represent molecules or other mobile objects and can be part of networks of processes that move simultaneously and interact in a given geometrical space. The calculus embeds collision detection and response, binding of compatible 3D processes and splitting of previously established bonds. In this work the full formal timed operational semantics of the calculus is provided, together with examples that illustrate the use of the calculus in a well-known biological scenario. Moreover, a result of well-formedness about the evolution of a given network of well-formed 3D processes is proved.
A Distributed Data Collection Algorithm for Wireless Sensor Networks with Persistent Storage Nodes
Venue: arXiv cs.NI 2010
Year: 2010

A distributed data collection algorithm to accurately store and forward information obtained by wireless sensor networks is proposed. The proposed algorithm does not depend on the sensor network topology, routing tables, or geographic locations of sensor nodes, but rather makes use of uniformly distributed storage nodes. Analytical and simulation results for this algorithm show that, with high probability, the data disseminated by the sensor nodes can be precisely collected by querying any small set of storage nodes.
System Virtualization and Efficient ID Transmission Method for RFID Tag Infrastructure Network
Venue: arXiv cs.NI 2010
Year: 2010

The use of RFID tag which identifies a thing and an object will be expanded with progress of ubiquitous society, and it is necessary to study how to construct RFID network system as a social infrastructure like the Internet. First, this paper proposes the virtualization method of RFID tag network system to enable the same physical RFID network system to be used by multiple different service systems. The system virtualization not only reduces the system cost but also can dramatically reduce the installation space of physical readers and the operation cost. It is proposed that all equipments in the RFID network system except RFID tag could be shared with the conventional virtual technologies. Then, this paper proposes the conditional tag ID processing and the efficient tag ID transmission method which can greatly reduce the processing time and processing load in RFID tag Infrastructure network The conditional tag ID processing allows that tag ID is valid only at a certain time zone of day or in a certain area. The efficient tag ID transmission method uses the virtual network address of the service center as a part of the ID of an RF tag, which allows the direct ID forwarding to the service center.
Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we study minimum cut and maximum flow problems on planar graphs, both in static and in dynamic settings. First, we present an algorithm that given an undirected planar graph computes the minimum cut between any two given vertices in O(n log log n) time. Second, we show how to achieve the same O(n log log n) bound for the problem of computing maximum flows in undirected planar graphs. To the best of our knowledge, these are the first algorithms for those two problems that break the O(n log n) barrier, which has been standing for more than 25 years. Third, we present a fully dynamic algorithm that is able to maintain information about minimum cuts and maximum flows in a plane graph (i.e., a planar graph with a fixed embedding): our algorithm is able to insert edges, delete edges and answer min-cut and max-flow queries between any pair of vertices in O(n^(2/3) log^3 n) time per operation. This result is based on a new dynamic shortest path algorithm for planar graphs which may be of independent interest. We remark that this is the first known non-trivial algorithm for min-cut and max-flow problems in a dynamic setting.
Towards Increase in Quality by Preprocessed Source Code and Measurement Analysis of Software Applications
Venue: arXiv cs.SE 2010
Year: 2010

In this paper two intensive problems faced during software application's analysis and development process arose by the software industry are briefly conversed i.e. identification of fault proneness and increase in rate of variability in the source code of traditional and product line applications. To contribute in the field of software application analysis and development, and to mitigate the aforementioned hurdles, a measurement analysis based approach is discussed in this paper. Furthermore, a prototype is developed based on the concepts of discussed approach i.e. analyzing preprocessed source code characteristics, identifying additional level of complexities using several procedural and object oriented source code measures and visualizing obtained results in different diagrams e.g. bar charts, file maps and graphs etc. Developed prototype is discussed in detail in this paper and validated by means of an experiment as well.
Bayesian Based Comment Spam Defending Tool
Venue: arXiv cs.CR 2010
Year: 2010

Spam messes up user's inbox, consumes network resources and spread worms and viruses. Spam is flooding of unsolicited, unwanted e mail. Spam in blogs is called blog spam or comment spam.It is done by posting comments or flooding spams to the services such as blogs, forums,news,email archives and guestbooks. Blog spams generally appears on guestbooks or comment pages where spammers fill a comment box with spam words. In addition to wasting user's time with unwanted comments, spam also consumes a lot of bandwidth. In this paper, we propose a software tool to prevent such blog spams by using Bayesian Algorithm based technique. It is derived from Bayes' Theorem. It gives an output which has a probability that any comment is spam, given that it has certain words in it. With using our past entries and a comment entry, this value is obtained and compared with a threshold value to find if it exceeds the threshold value or not. By using this concept, we developed a software tool to block comment spam. The experimental results show that the Bayesian based tool is working well. This paper has the major findings and their significance of blog spam filter.
The Inverse Task of the Reflexive Game Theory: Theoretical Matters, Practical Applications and Relationship with Other Issues
Venue: arXiv cs.MA 2010
Year: 2010

The Reflexive Game Theory (RGT) has been recently proposed by Vladimir Lefebvre to model behavior of individuals in groups. The goal of this study is to introduce the Inverse task. We consider methods of solution together with practical applications. We present a brief overview of the RGT for easy understanding of the problem. We also develop the schematic representation of the RGT inference algorithms to create the basis for soft- and hardware solutions of the RGT tasks. We propose a unified hierarchy of schemas to represent humans and robots. This hierarchy is considered as a unified framework to solve the entire spectrum of the RGT tasks. We conclude by illustrating how this framework can be applied for modeling of mixed groups of humans and robots. All together this provides the exhaustive solution of the Inverse task and clearly illustrates its role and relationships with other issues considered in the RGT.
Counting Colours in Compressed Strings
Venue: arXiv cs.DS 2010
Year: 2010

Suppose we are asked to preprocess a string \(s [1..n]\) such that later, given a substring's endpoints, we can quickly count how many distinct characters it contains. In this paper we give a data structure for this problem that takes \(n H_0 (s) + \Oh{n} + \oh{n H_0 (s)}\) bits, where \(H_0 (s)\) is the 0th-order empirical entropy of $s$, and answers queries in $\Oh{\log^{1 + ε} n}$ time for any constant \(ε> 0\). We also show how our data structure can be made partially dynamic.
Approaching Throughput-optimality in Distributed CSMA Scheduling Algorithms with Collisions
Venue: arXiv cs.NI 2010
Year: 2010

It was shown recently that CSMA (Carrier Sense Multiple Access)-like distributed algorithms can achieve the maximal throughput in wireless networks (and task processing networks) under certain assumptions. One important, but idealized assumption is that the sensing time is negligible, so that there is no collision. In this paper, we study more practical CSMA-based scheduling algorithms with collisions. First, we provide a Markov chain model and give an explicit throughput formula which takes into account the cost of collisions and overhead. The formula has a simple form since the Markov chain is "almost" time-reversible. Second, we propose transmission-length control algorithms to approach throughput optimality in this case. Sufficient conditions are given to ensure the convergence and stability of the proposed algorithms. Finally, we characterize the relationship between the CSMA parameters (such as the maximum packet lengths) and the achievable capacity region.
Dynamic Magic Sets for Super-Consistent Answer Set Programs
Venue: arXiv cs.LO 2010
Year: 2010

For many practical applications of ASP, for instance data integration or planning, query answering is important, and therefore query optimization techniques for ASP are of great interest. Magic Sets are one of these techniques, originally defined for Datalog queries (ASP without disjunction and negation). Dynamic Magic Sets (DMS) are an extension of this technique, which has been proved to be sound and complete for query answering over ASP programs with stratified negation. A distinguishing feature of DMS is that the optimization can be exploited also during the nondeterministic phase of ASP engines. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space, which may result in exponential performance gains. In this paper, the correctness of DMS is formally established and proved for brave and cautious reasoning over the class of super-consistent ASP programs (ASP^{sc} programs). ASP^{sc} programs guarantee consistency (i.e., have answer sets) when an arbitrary set of facts is added to them. This result generalizes the applicability of DMS, since the class of ASP^{sc} programs is richer than ASP programs with stratified negation, and in particular includes all odd-cycle-free programs. DMS has been implemented as an extension of DLV, and the effectiveness of DMS for ASP^{sc} programs is empirically confirmed by experimental results with this system.
Compressed Transmission of Route Descriptions
Venue: arXiv cs.DS 2010
Year: 2010

We present two methods to compress the description of a route in a road network, i.e., of a path in a directed graph. The first method represents a path by a sequence of via edges. The subpaths between the via edges have to be unique shortest paths. Instead of via edges also via nodes can be used, though this requires some simple preprocessing. The second method uses contraction hierarchies to replace subpaths of the original path by shortcuts. The two methods can be combined with each other. Also, we propose the application to mobile server based routing: We compute the route on a server which has access to the latest information about congestions for example. Then we transmit the computed route to the car using some mobile radio communication. There, we apply the compression to save costs and transmission time. If the compression works well, we can transmit routes even when the bandwidth is low. Although we have not evaluated our ideas with realistic data yet, they are quite promising.