OpenRaiser/Intern-Atlas huggingface dataset:
Evolution of Ideas: A Novel Memetic Algorithm Based on Semantic Networks
Venue: arXiv cs.NE 2012
Year: 2012

This paper presents a new type of evolutionary algorithm (EA) based on the concept of "meme", where the individuals forming the population are represented by semantic networks and the fitness measure is defined as a function of the represented knowledge. Our work can be classified as a novel memetic algorithm (MA), given that (1) it is the units of culture, or information, that are undergoing variation, transmission, and selection, very close to the original sense of memetics as it was introduced by Dawkins; and (2) this is different from existing MA, where the idea of memetics has been utilized as a means of local refinement by individual learning after classical global sampling of EA. The individual pieces of information are represented as simple semantic networks that are directed graphs of concepts and binary relations, going through variation by memetic versions of operators such as crossover and mutation, which utilize knowledge from commonsense knowledge bases. In evaluating this introductory work, as an interesting fitness measure, we focus on using the structure mapping theory of analogical reasoning from psychology to evolve pieces of information that are analogous to a given base information. Considering other possible fitness measures, the proposed representation and algorithm can serve as a computational tool for modeling memetic theories of knowledge, such as evolutionary epistemology and cultural selection theory.
Ultrametric Model of Mind, II: Application to Text Content Analysis
Venue: arXiv cs.AI 2012
Year: 2012

In a companion paper, Murtagh (2012), we discussed how Matte Blanco's work linked the unrepressed unconscious (in the human) to symmetric logic and thought processes. We showed how ultrametric topology provides a most useful representational and computational framework for this. Now we look at the extent to which we can find ultrametricity in text. We use coherent and meaningful collections of nearly 1000 texts to show how we can measure inherent ultrametricity. On the basis of our findings we hypothesize that inherent ultrametricty is a basis for further exploring unconscious thought processes.
Nonparametric Sparse Representation
Venue: arXiv cs.CV 2012
Year: 2012

This paper suggests a nonparametric scheme to find the sparse solution of the underdetermined system of linear equations in the presence of unknown impulsive or non-Gaussian noise. This approach is robust against any variations of the noise model and its parameters. It is based on minimization of rank pseudo norm of the residual signal and l_1-norm of the signal of interest, simultaneously. We use the steepest descent method to find the sparse solution via an iterative algorithm. Simulation results show that our proposed method outperforms the existence methods like OMP, BP, Lasso, and BCS whenever the observation vector is contaminated with measurement or environmental non-Gaussian noise with unknown parameters. Furthermore, for low SNR condition, the proposed method has better performance in the presence of Gaussian noise.
On Ergodic Secrecy Capacity of Multiple Input Wiretap Channel with Statistical CSIT
Venue: arXiv cs.IT 2012
Year: 2012

We consider the secure transmission in ergodic fast-Rayleigh fading multiple-input single-output single-antennaeavesdropper (MISOSE) wiretap channels. We assume that the statistics of both the legitimate and eavesdropper channels is the only available channel state information at the transmitter (CSIT). By introducing a new secrecy capacity upper bound, we prove that the secrecy capacity is achieved by Gaussian input without prefixing. To attain this, we form another MISOSE channel for upper-bounding, and tighten the bound by finding the worst correlations between the legitimate and eavesdropper channel coefficients. The resulting upper bound is tighter than the others in the literature which are based on modifying the correlation between the noises at the legitimate receiver and eavesdropper. Next, we fully characterize the ergodic secrecy capacity by showing that the optimal channel input covariance matrix is a scaled identity matrix, with the transmit power allocated uniformly among the antennas. The key to solve such a complicated stochastic optimization problem is by exploiting the completely monotone property of the ergodic secrecy capacity to use the stochastic ordering theory. Finally, our simulation results show that for the considered channel setting, the secrecy capacity is bounded in both the high signal-to-noise ratio and large number of transmit antenna regimes.
NegCut: Automatic Image Segmentation based on MRF-MAP
Venue: arXiv cs.CV 2012
Year: 2012

Solving the Maximum a Posteriori on Markov Random Field, MRF-MAP, is a prevailing method in recent interactive image segmentation tools. Although mathematically explicit in its computational targets, and impressive for the segmentation quality, MRF-MAP is hard to accomplish without the interactive information from users. So it is rarely adopted in the automatic style up to today. In this paper, we present an automatic image segmentation algorithm, NegCut, based on the approximation to MRF-MAP. First we prove MRF-MAP is NP-hard when the probabilistic models are unknown, and then present an approximation function in the form of minimum cuts on graphs with negative weights. Finally, the binary segmentation is taken from the largest eigenvector of the target matrix, with a tuned version of the Lanczos eigensolver. It is shown competitive at the segmentation quality in our experiments.
Social Norm Design for Information Exchange Systems with Limited Observations
Venue: arXiv cs.GT 2012
Year: 2012

Information exchange systems differ in many ways, but all share a common vulnerability to selfish behavior and free-riding. In this paper, we build incentives schemes based on social norms. Social norms prescribe a social strategy for the users in the system to follow and deploy reputation schemes to reward or penalize users depending on their behaviors. Because users in these systems often have only limited capability to observe the global system information, e.g. the reputation distribution of the users participating in the system, their beliefs about the reputation distribution are heterogeneous and biased. Such belief heterogeneity causes a positive fraction of users to not follow the social strategy. In such practical scenarios, the standard equilibrium analysis deployed in the economics literature is no longer directly applicable and hence, the system design needs to consider these differences. To investigate how the system designs need to change when the participating users have only limited observations, we focus on a simple social norm with binary reputation labels but allow adjusting the punishment severity through randomization. First, we model the belief heterogeneity using a suitable Bayesian belief function. Next, we formalize the users' optimal decision problems and derive in which scenarios they follow the prescribed social strategy. With this result, we then study the system dynamics and formally define equilibrium in the sense that the system is stable when users strategically optimize their decisions. By rigorously studying two specific cases where users' belief distribution is constant or is linearly influenced by the true reputation distribution, we prove that the optimal reputation update rule is to choose the mildest possible punishment. This result is further confirmed for higher order beliefs in simulations.
Finding Convex Hulls Using Quickhull on the GPU
Venue: arXiv cs.CG 2012
Year: 2012

We present a convex hull algorithm that is accelerated on commodity graphics hardware. We analyze and identify the hurdles of writing a recursive divide and conquer algorithm on the GPU and divise a framework for representing this class of problems. Our framework transforms the recursive splitting step into a permutation step that is well-suited for graphics hardware. Our convex hull algorithm of choice is Quickhull. Our parallel Quickhull implementation (for both 2D and 3D cases) achieves an order of magnitude speedup over standard computational geometry libraries.
Robust Transceiver Design for AF MIMO Relay Systems with Column Correlations
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we investigate the robust transceiver design for dual-hop amplify-and-forward (AF) MIMO relay systems with Gaussian distributed channel estimation errors. Aiming at maximizing the mutual information under imperfect channel state information (CSI), source precoder at source and forwarding matrix at the relay are jointly optimized. Using some elegant attributes of matrix-monotone functions, the structures of the optimal solutions are derived first. Then based on the derived structure an iterative waterfilling solution is proposed. Several existing algorithms are shown to be special cases of the proposed solution. Finally, the effectiveness of the proposed robust design is demonstrated by simulation results.
Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation
Venue: arXiv cs.IT 2012
Year: 2012

We investigate spatially coupled code ensembles. For transmission over the binary erasure channel, it was recently shown that spatial coupling increases the belief propagation threshold of the ensemble to essentially the maximum a-priori threshold of the underlying component ensemble. This explains why convolutional LDPC ensembles, originally introduced by Felstrom and Zigangirov, perform so well over this channel. We show that the equivalent result holds true for transmission over general binary-input memoryless output-symmetric channels. More precisely, given a desired error probability and a gap to capacity, we can construct a spatially coupled ensemble which fulfills these constraints universally on this class of channels under belief propagation decoding. In fact, most codes in that ensemble have that property. The quantifier universal refers to the single ensemble/code which is good for all channels but we assume that the channel is known at the receiver. The key technical result is a proof that under belief propagation decoding spatially coupled ensembles achieve essentially the area threshold of the underlying uncoupled ensemble. We conclude by discussing some interesting open problems.
Performance Analysis of Beacon-Less IEEE 802.15.4 Multi-Hop Networks
Venue: arXiv cs.NI 2012
Year: 2012

We develop an approximate analytical technique for evaluating the performance of multi-hop networks based on beacon-less CSMA/CA as standardised in IEEE 802.15.4, a popular standard for wireless sensor networks. The network comprises sensor nodes, which generate measurement packets, and relay nodes which only forward packets. We consider a detailed stochastic process at each node, and analyse this process taking into account the interaction with neighbouring nodes via certain unknown variables (e.g., channel sensing rates, collision probabilities, etc.). By coupling these analyses of the various nodes, we obtain fixed point equations that can be solved numerically to obtain the unknown variables, thereby yielding approximations of time average performance measures, such as packet discard probabilities and average queueing delays. Different analyses arise for networks with no hidden nodes and networks with hidden nodes. We apply this approach to the performance analysis of tree networks rooted at a data sink. Finally, we provide a validation of our analysis technique against simulations.
Power Allocation and Pricing in Multi-User Relay Networks Using Stackelberg and Bargaining Games
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers a multi-user single-relay wireless network, where the relay gets paid for helping the users forward signals, and the users pay to receive the relay service. We study the relay power allocation and pricing problems, and model the interaction between the users and the relay as a two-level Stackelberg game. In this game, the relay, modeled as the service provider and the leader of the game, sets the relay price to maximize its revenue; while the users are modeled as customers and the followers who buy power from the relay for higher transmission rates. We use a bargaining game to model the negotiation among users to achieve a fair allocation of the relay power. Based on the proposed fair relay power allocation rule, the optimal relay power price that maximizes the relay revenue is derived analytically. Simulation shows that the proposed power allocation scheme achieves higher network sum-rate and relay revenue than the even power allocation. Furthermore, compared with the sum-rate-optimal solution, simulation shows that the proposed scheme achieves better fairness with comparable network sum-rate for a wide range of network scenarios. The proposed pricing and power allocation solutions are also shown to be consistent with the laws of supply and demand.
Stability of the Max-Weight Protocol in Adversarial Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

In this paper we consider the Max-Weight protocol for routing and scheduling in wireless networks under an adversarial model. This protocol has received a significant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal whenever the traffic patterns and propagation conditions are governed by a stationary stochastic process. However, the standard proof of throughput optimality (which is based on the negative drift of a quadratic potential function) does not hold when the traffic patterns and the edge capacity changes over time are governed by an arbitrary adversarial process. Such an environment appears frequently in many practical wireless scenarios when the assumption that channel conditions are governed by a stationary stochastic process does not readily apply. In this paper we prove that even in the above adversarial setting, the Max-Weight protocol keeps the queues in the network stable (i.e. keeps the queue sizes bounded) whenever this is feasible by some routing and scheduling algorithm. However, the proof is somewhat more complex than the negative potential drift argument that applied in the stationary case. Our proof holds for any arbitrary interference relationships among edges. We also prove the stability of $\ep$-approximate Max-Weight under the adversarial model. We conclude the paper with a discussion of queue sizes in the adversarial model as well as a set of simulation results.
Tacit knowledge mining algorithm based on linguistic truth-valued concept lattice
Venue: arXiv cs.AI 2012
Year: 2012

This paper is the continuation of our research work about linguistic truth-valued concept lattice. In order to provide a mathematical tool for mining tacit knowledge, we establish a concrete model of 6-ary linguistic truth-valued concept lattice and introduce a mining algorithm through the structure consistency. Specifically, we utilize the attributes to depict knowledge, propose the 6-ary linguistic truth-valued attribute extended context and congener context to characterize tacit knowledge, and research the necessary and sufficient conditions of forming tacit knowledge. We respectively give the algorithms of generating the linguistic truth-valued congener context and constructing the linguistic truth-valued concept lattice.
Polynomial-Time, Semantically-Secure Encryption Achieving the Secrecy Capacity
Venue: arXiv cs.IT 2012
Year: 2012

In the wiretap channel setting, one aims to get information-theoretic privacy of communicated data based only on the assumption that the channel from sender to receiver is noisier than the one from sender to adversary. The secrecy capacity is the optimal (highest possible) rate of a secure scheme, and the existence of schemes achieving it has been shown. For thirty years the ultimate and unreached goal has been to achieve this optimal rate with a scheme that is polynomial-time. (This means both encryption and decryption are proven polynomial time algorithms.) This paper finally delivers such a scheme. In fact it does more. Our scheme not only meets the classical notion of security from the wiretap literature, called MIS-R (mutual information security for random messages) but achieves the strictly stronger notion of semantic security, thus delivering more in terms of security without loss of rate.
Component Coloring of Proper Interval Graphs and Split Graphs
Venue: arXiv cs.DM 2012
Year: 2012

We introduce a generalization of the well known graph (vertex) coloring problem, which we call the problem of \emph{component coloring of graphs}. Given a graph, the problem is to color the vertices using minimum number of colors so that the size of each connected component of the subgraph induced by the vertices of the same color does not exceed $C$. We give a linear time algorithm for the problem on proper interval graphs. We extend this algorithm to solve two weighted versions of the problem in which vertices have integer weights. In the \emph{splittable} version the weights of vertices can be split into differently colored parts, however, the total weight of a monochromatic component cannot exceed $C$. For this problem on proper interval graphs we give a polynomial time algorithm. In the \emph{non-splittable} version the vertices cannot be split. Using the algorithm for the splittable version we give a 2-approximation algorithm for the non-splittable problem on proper interval graphs which is NP-hard. We also prove that even the unweighted version of the problem is NP-hard for split graphs.
Multi-scale Community Detection using Stability Optimisation within Greedy Algorithms
Venue: arXiv cs.DS 2012
Year: 2012

Many real systems can be represented as networks whose analysis can be very informative regarding the original system's organisation. In the past decade community detection received a lot of attention and is now an active field of research. Recently stability was introduced as a new measure for partition quality. This work investigates stability as an optimisation criterion that exploits a Markov process view of networks to enable multi-scale community detection. Several heuristics and variations of an algorithm optimising stability are presented as well as an application to overlapping communities. Experiments show that the method enables accurate multi-scale network analysis.
Notes on Bit-reversal Broadcast Scheduling
Venue: arXiv cs.DS 2012
Year: 2012

This report contains revision and extension of some results about RBO [arXiv:1108.5095]. RBO is a simple and efficient broadcast scheduling of $n = 2^k$ uniform frames for battery powered radio receivers. Each frame contains a key from some arbitrary linearly ordered universe. The broadcast cycle -- a sequence of frames sorted by the keys and permuted by $k$-bit reversal -- is transmitted in a round robin fashion by the broadcaster. At arbitrary time during the transmission, the receiver may start a simple protocol that reports to him all the frames with the keys that are contained in a specified interval of the key values $[K', K"]$. RBO receives at most $2 k + 1$ other frames' keys before receiving the first key from $[K', K"]$ or noticing that there are no such keys in the broadcast cycle. As a simple corollary, $4 k + 2$ is upper bound the number of keys outside $[K', K"]$ that will ever be received. In unreliable network the expected number of efforts to receive such frames is bounded by $(8 k + 4) / p + 2 (1 - p) / p^2$, where $p$ is probability of successful reception, and the reception rate of the requested frames is $p$ -- the highest possible. The receiver's protocol state consists of the values $k$, $K'$ and $K"$, one wake-up timer and two other $k$-bit variables. Its only nontrivial computation -- the computation of the next wake-up time slot -- can be performed in $O (k)$ simple operations, such as arithmetic/bit-wise operations on $k$-bit numbers, using only constant number of $k$-bit variables.
On Some Entertaining Applications of the Concept of Set in Computer Science Course
Venue: arXiv cs.OH 2012
Year: 2012

Some aspects of programming education are examined in this work. It is emphasised, based on the entertainment value, the most appropriate examples are chosen to demonstrate the different language constructions and data structures. Such an example is the demonstrated algorithm for solving the widespread nowadays "Sudoku" puzzle. This is made, because of the connection with the term set and putting it into practice in the programming. Using the so built program there are solved some combinatorial problems, connected to the Sudoku matrices. Key words: Education in programming, programming languages, data structures, set, Sudoku matrix, Sudoku puzzle.
Characterizing Interdisciplinarity of Researchers and Research Topics Using Web Search Engines
Venue: arXiv cs.SI 2012
Year: 2012

Researchers' networks have been subject to active modeling and analysis. Earlier literature mostly focused on citation or co-authorship networks reconstructed from annotated scientific publication databases, which have several limitations. Recently, general-purpose web search engines have also been utilized to collect information about social networks. Here we reconstructed, using web search engines, a network representing the relatedness of researchers to their peers as well as to various research topics. Relatedness between researchers and research topics was characterized by visibility boost-increase of a researcher's visibility by focusing on a particular topic. It was observed that researchers who had high visibility boosts by the same research topic tended to be close to each other in their network. We calculated correlations between visibility boosts by research topics and researchers' interdisciplinarity at individual level (diversity of topics related to the researcher) and at social level (his/her centrality in the researchers' network). We found that visibility boosts by certain research topics were positively correlated with researchers' individual-level interdisciplinarity despite their negative correlations with the general popularity of researchers. It was also found that visibility boosts by network-related topics had positive correlations with researchers' social-level interdisciplinarity. Research topics' correlations with researchers' individual- and social-level interdisciplinarities were found to be nearly independent from each other. These findings suggest that the notion of "interdisciplinarity" of a researcher should be understood as a multi-dimensional concept that should be evaluated using multiple assessment means.
Modelling and simulation of complex systems: an approach based on multi-level agents
Venue: arXiv cs.MA 2012
Year: 2012

A complex system is made up of many components with many interactions. So the design of systems such as simulation systems, cooperative systems or assistance systems includes a very accurate modelling of interactional and communicational levels. The agent-based approach provides an adapted abstraction level for this problem. After having studied the organizational context and communicative capacities of agentbased systems, to simulate the reorganization of a flexible manufacturing, to regulate an urban transport system, and to simulate an epidemic detection system, our thoughts on the interactional level were inspired by human-machine interface models, especially those in "cognitive engineering". To provide a general framework for agent-based complex systems modelling, we then proposed a scale of four behaviours that agents may adopt in their complex systems (reactive, routine, cognitive, and collective). To complete the description of multi-level agent models, which is the focus of this paper, we illustrate our modelling and discuss our ongoing work on each level.