Message-passing for inference and optimization of real variables on sparse graphs

The inference and optimization in sparse graphs with real variables is studied using methods of statistical mechanics. Efficient distributed algorithms for the resource allocation problem are devised. Numerical simulations show excellent performance and full agreement with the theoretical results. © Springer-Verlag Berlin Heidelberg 2006.

Typical performance of regular low-density parity-check codes over general symmetric channels

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. Relationship between the free energy in statistical-mechanics approach and the mutual information used in the information-theory literature is established within a general framework; Gallager and MacKay-Neal codes are studied as specific examples of LDPC codes. It is shown that basic properties of these codes known for particular channels, including their potential to saturate Shannon's bound, hold for general symmetric channels. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel models.

On the Vertex Separation of Cactus Graphs

This paper is part of a work in progress whose goal is to construct a fast, practical algorithm for the vertex separation (VS) of cactus graphs. We prove a \main theorem for cacti", a necessary and sufficient condition for the VS of a cactus graph being k. Further, we investigate the ensuing ramifications that prevent the construction of an algorithm based on that theorem only.

On Graph-Based Cryptography and Symbolic Computations

We have been investigating the cryptographical properties of in nite families of simple graphs of large girth with the special colouring of vertices during the last 10 years. Such families can be used for the development of cryptographical algorithms (on symmetric or public key modes) and turbocodes in error correction theory. Only few families of simple graphs of large unbounded girth and arbitrarily large degree are known. The paper is devoted to the more general theory of directed graphs of large girth and their cryptographical applications. It contains new explicit algebraic constructions of in finite families of such graphs. We show that they can be used for the implementation of secure and very fast symmetric encryption algorithms. The symbolic computations technique allow us to create a public key mode for the encryption scheme based on algebraic graphs.

Some MDS Codes over Gf(64) Connected with the Binary Doubly-Even [72,36,16] Code

* The author is supported by a Return Fellowship from the Alexander von Humboldt Foundation.

On the Vertex Separation of Maximal Outerplanar Graphs

We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.

New Binary $[70,35,12]$ Self-Dual and Binary $[72,36,12]$ Self-Dual Doubly-Even Codes

∗ This work was supported in part by the Bulgarian NSF under Grant MM-901/99

New Symmetric (61,16,4) Designs Invariant Under the Dihedral Group of Order 10

∗ This work has been partially supported by the Bulgarian NSF under Contract No. I-506/1995.

An improved memory management scheme for large scale graph computing engine GraphChi

GraphChi is the first reported disk-based graph engine that can handle billion-scale graphs on a single PC efficiently. GraphChi is able to execute several advanced data mining, graph mining and machine learning algorithms on very large graphs. With the novel technique of parallel sliding windows (PSW) to load subgraph from disk to memory for vertices and edges updating, it can achieve data processing performance close to and even better than those of mainstream distributed graph engines. GraphChi mentioned that its memory is not effectively utilized with large dataset, which leads to suboptimal computation performances. In this paper we are motivated by the concepts of 'pin ' from TurboGraph and 'ghost' from GraphLab to propose a new memory utilization mode for GraphChi, which is called Part-in-memory mode, to improve the GraphChi algorithm performance. The main idea is to pin a fixed part of data inside the memory during the whole computing process. Part-in-memory mode is successfully implemented with only about 40 additional lines of code to the original GraphChi engine. Extensive experiments are performed with large real datasets (including Twitter graph with 1.4 billion edges). The preliminary results show that Part-in-memory mode memory management approach effectively reduces the GraphChi running time by up to 60% in PageRank algorithm. Interestingly it is found that a larger portion of data pinned in memory does not always lead to better performance in the case that the whole dataset cannot be fitted in memory. There exists an optimal portion of data which should be kept in the memory to achieve the best computational performance.

Learning Technology in Scheduling Based on the Mixed Graphs

We propose the adaptive algorithm for solving a set of similar scheduling problems using learning technology. It is devised to combine the merits of an exact algorithm based on the mixed graph model and heuristics oriented on the real-world scheduling problems. The former may ensure high quality of the solution by means of an implicit exhausting enumeration of the feasible schedules. The latter may be developed for certain type of problems using their peculiarities. The main idea of the learning technology is to produce effective (in performance measure) and efficient (in computational time) heuristics by adapting local decisions for the scheduling problems under consideration. Adaptation is realized at the stage of learning while solving a set of sample scheduling problems using a branch-and-bound algorithm and structuring knowledge using pattern recognition apparatus.

On Multi-Dimensional Random Walk Models Approximating Symmetric Space-Fractional Diffusion Processes

Mathematics Subject Classification: 26A33, 47B06, 47G30, 60G50, 60G52, 60G60.

The topics they are a-changing - characterising topics with time-stamped semantic graphs

DBpedia has become one of the major sources of structured knowledge extracted from Wikipedia. Such structures gradually re-shape the representation of Topics as new events relevant to such topics emerge. Such changes make evident the continuous evolution of topic representations and introduce new challenges to supervised topic classification tasks, since labelled data can rapidly become outdated. Here we analyse topic changes in DBpedia and propose the use of semantic features as a more stable representation of a topic. Our experiments show promising results in understanding how the relevance of features to a topic changes over time.

Shortest node-disjoint paths on random graphs

A localized method to distribute paths on random graphs is devised, aimed at finding the shortest paths between given source/destination pairs while avoiding path overlaps at nodes. We propose a method based on message-passing techniques to process global information and distribute paths optimally. Statistical properties such as scaling with system size and number of paths, average path-length and the transition to the frustrated regime are analyzed. The performance of the suggested algorithm is evaluated through a comparison against a greedy algorithm. © 2014 IOP Publishing Ltd and SISSA Medialab srl.

Conjugate Compositions in Even-Dimensional Affinely Connected Spaces without a Torsion

Let in even-dimensional a±nely connected space without a torsion A2m be given a composition Xm£Xm by the affinor a¯ ®. The affinor b¯ ®, determined with the help of the eigen-vectors of the matrix (a¯ ®), de¯nes the second composition Ym £ Y m. Conjugate compositions are introduced by the condition: the a±nors of any of both compositions transform the vectors from the one position of the composition, generated by the other a±nor, in the vectors from the another its position. It is proved that the compositions de¯ne by a±nors a¯ ® and b¯ ® are conjugate. It is proved also that if the composition Xm£Xm is Cartesian and composition Ym£Y m is Cartesian or chebyshevian, or geodesic than the space A2m is affine.

Natural Connections with Totally Skew-Symmetric Torsion on Manifolds with Norden-Type Metrics

This paper is a survey of results obtained by the authors on the geometry of connections with totally skew-symmetric torsion on the following manifolds: almost complex manifolds with Norden metric, almost contact manifolds with B-metric and almost hypercomplex manifolds with Hermitian and anti-Hermitian metric.