Search

Community detection is a key to understanding the structure of complex networks. Many community detection approaches have been proposed based on the modularity optimization. Algorithms that optimize one initial solution often get into local optima, but algorithms that simultaneously optimize a population of solutions have high computational complexity. To solve these problems, genetic algorithms improved by a local learning procedure known as memetic algorithms can be applied. We propose a memetic algorithm for community detection in networks, that exploits node entropy for local learning. Node entropy is easy to use to speed up the convergence of an evolutionary algorithm and to increase the quality of partitions, while it uses only the node’s neighborhood and does not require any threshold value. Moreover, this algorithm is slightly modified in order to avoid modularity function which suffers a resolution limit and, therefore, it may fail to detect small communities. We propose and use an entropy function as an optimization function and as criteria in grouping crossover operator. Experiments on real-world and synthetic networks illustrate that the proposed method can find natural partitions effectively. [ABSTRACT FROM AUTHOR]

This paper considers the suitability of string transformation techniques for lossless chain codes' compression. The more popular chain codes are compressed including the Freeman chain code in four and eight directions, the vertex chain code, the three orthogonal chain code, and the normalised directional chain code. A testing environment consisting of the constant 0-symbol Run-Length Encoding ( RLE 0 L ), Move-To-Front Transformation (MTFT), and Burrows–Wheeler Transform (BWT) is proposed in order to develop a more suitable configuration of these techniques for each type of the considered chain code. Finally, a simple yet efficient entropy coding is proposed consisting of MTFT, followed by the chain code symbols' binarisation and the run-length encoding. PAQ8L compressor is also an option that can be considered in the final compression stage. Comparisons were done between the state-of-the-art including the Universal Chain Code Compression algorithm, Move-To-Front based algorithm, and an algorithm, based on the Markov model. Interesting conclusions were obtained from the experiments: the sequential uses of MTFT, RLE 0 L , and BWT are reasonable only in the cases of shorter chain codes' alphabets as with the vertex chain code and the three orthogonal chain code. For the remaining chain codes, BWT alone provided the best results. The experiments confirm that the proposed approach is comparable against other lossless chain code compression methods, while in total achieving higher compression rates. [ABSTRACT FROM AUTHOR]

Burrows-Wheeler Transform, followed by Move-To-Front Transform, are often used transformation techniques in data compression. They may reduce the information entropy of the input sequence, which becomes more compressible in this way. This paper suggests an alternative, a Prediction-based Move-To-Front Transform, which may replace the aforementioned transformations. According to the context, consisting of a few already seen symbols, the Prediction-based Move-To-Front Transform selects an appropriate ordered domain of symbols to achieve a better match with the currently transforming symbol. Freeman chain code in four and eight directions, Three-Orthogonal chain code, and Vertex Chain Code were used for experiments. We confirmed that the proposed approach, when using an appropriate length of context, reduces the information entropy to a similar extent as the Burrows-Wheeler Transform followed by the Move-To-Front Transform on chain code data. Both approaches led to a very similar compression efficiency on 32 testing shapes when an arithmetic coder was used in the final stage. The proposed approach turned out to be more efficient when longer chain code sequences were used, obtained by merging all the testing chain codes of the same type. [ABSTRACT FROM AUTHOR]

This paper considers the use of interpolative coding for lossless chain code compression. The most popular chain codes are used, including Freeman chain code in eight (F8) and four directions (F4), Vertex Chain Code (VCC), and three-orthogonal chain code (3OT). The whole compression pipeline consists of the Burrows–Wheeler transform, Move-To-Front transform and the interpolative coding, which was improved by FELICS and new Ψ-coding. The approach was compared with the state-of-the-art chain code compression algorithms. For VCC, 3OT and F4, the obtained results are slightly better than the existing approaches. However, an important improvement was achieved with F8 chain code, where the presented approach is considerably better. [ABSTRACT FROM AUTHOR]