Fuzzy fractal dimension of complex networks

Complex networks are widely used to describe the structure of many complex systems in nature and society. The box-covering algorithm is widely applied to calculate the fractal dimension, which plays an important role in complex networks. However, there are two open issues in the existing box-covering algorithms. On the one hand, to identify the minimum boxes for any given size belongs to a family of Non-deterministic Polynomial-time hard problems. On the other hand, there exists randomness. In this paper, a fuzzy fractal dimension model of complex networks with fuzzy sets is proposed. The results are illustrated to show that the proposed model is efficient and less time consuming.     

网络维数:一种度量复杂网络的新方法

如何对复杂网络进行刻画与度量,一直是人们关注的热点。在研究自相似复杂网络分形维数的基础上,提出了一种度量复杂网络的新方法——网络维数,即复杂网络边权重和的对数值与节点权重和的对数值的比值,可以将边权重及点权重推广到实数域和复数域;同时给出了不同类型权重对应的网络维数的计算方法;最后以几个代表性的经典复杂网络模型为例,讨论了所提出的网络维数的若干性质。     

A multiobjective box-covering algorithm for fractal modularity on complex networks

The box-covering method is widely used on measuring the fractal property on complex networks. The problem of finding the minimum number of boxes to tile a network is known as a NP-hard problem. Many algorithms have been proposed to solve this problem. All the current box-covering algorithms regard the box number minimization as the only objective. However, the fractal modularity of the network partition divided by the box-covering method, has been proved to be strongly related to the information transportation in complex networks. Maximizing the fractal modularity is also important in the box-covering method, which can be divided into two objectives: maximization of ratio association and minimization of ratio cut. In this paper, to solve the dilemma of minimizing the box number and maximizing the fractal modularity at the same time, a multiobjective discrete particle swarm optimization box-covering (MOPSOBC) algorithm is proposed. The MOPSOBC algorithm applies the decomposition approach on the two objectives to approximate the Pareto front. The proposed MOPSOBC algorithm has been applied to six benchmark networks and compared with the state-of-the-art algorithms, including two classical box-covering algorithms, four single objective optimization algorithms and six multiobjective optimization algorithms. The experimental results show that the MOPSOBC algorithm can get similar box numbers with the current best algorithm, and it outperforms the state-of-the-art algorithms on the fractal modularity and normalized mutual information.     

Detecting patterns in process data with fractal dimension

In quality control discipline, pattern classification is focused on the detection of unnatural patterns in process data. In this paper, fractal dimension is proposed as a new classifier for pattern classification. Fractal dimension is an index for measuring the complexity of an object. Its applications were found in such diverse fields as manufacturing, material science, medical, and image processing. A method for detecting patterns in process data using the fractal dimension is proposed in this paper. A Monte Carlo study was carried out to study the fractal dimension (D) and the Y-intercept (Y_int) values of process data with patterns of interest. The patterns included in the study are natural pattern, upward linear trend, downward linear trend, cycle, systematic variable, stratification, mixture, upward sudden shift, and downward sudden shift. Based on the results, the approach is effective in detecting such non-periodic patterns as the natural patterns, linear trends (at slope ≥0.2), systematic variable, stratification, mixture, and sudden shifts. For the cyclical pattern, although the D and Y_int-values are not stable, the approach can provide useful information when the period of the cycle is greater than 2 and is less than or equal to half the window size (2N/2). The minor drawbacks of this approach are that it is not sensitive for detecting linear trends with small slope and the slope of the original data is needed to detect the difference between upward and downward linear trends and the difference between upward and downward sudden shifts.     

A comparison of fractal dimension estimators based on multiple surface generation algorithms

Fractal geometry has been actively researched in a variety of disciplines. The essential concept of fractal analysis is fractal dimension. It is easy to compute the fractal dimension of truly self-similar objects. Difficulties arise, however, when we try to compute the fractal dimension of surfaces that are not strictly self-similar. A number of fractal surface dimension estimators have been developed. However, different estimators lead to different results. In this paper, we compared five fractal surface dimension estimators (triangular prism, isarithm, variogram, probability, and variation) using surfaces generated from three surface generation algorithms (shear displacement, Fourier filtering, and midpoint displacement). We found that in terms of the standard deviations and the root mean square errors, the triangular prism and isarithm estimators perform the best among the five methods studied.     

Internet路由级拓扑的自相似分形统计

由于多角度多度量的统计方法存在种种问题,提出了通过分形维数从整体上刻画互联网拓扑性质。以传统分形理论为基础,结合互联网拓扑所具有的自相似性质,给出网络拓扑维数的相关概念,并通过网络拓扑与欧氏空间的映射关系,对拓扑维数进行了深入的解释。分析了理想分形拓扑的迭代膨胀过程,指出简单分形方法的不足,并进一步给出加权分形的相关定义及计算方法。通过统计互联网路由级拓扑的几个主要特征量,分析了拓扑维数与传统统计度量方法的关系,说明了拓扑维数在适用于统计观察互联网宏观拓扑的整体特性方面的作用。     

UJA-3DFD: A program to compute the 3D fractal dimension from MRI data

This work presents a computer program for computing the 3D fractal dimension (3DFD) from magnetic-resonance images of the brain. The program is based on an algorithm that calculates the 3D box counting of the entire volume of the brain, and also of its 3D skeletonization. The validity and accuracy of the software has been confirmed using solids with well-known 3DFD values. The usefulness of the program developed is demonstrated by its successful characterization of several neurodegenerative diseases.     

An improved box-counting method for image fractal dimension estimation

Fractal dimension (FD) is a useful feature for texture segmentation, shape classification, and graphic analysis in many fields. The box-counting approach is one of the frequently used techniques to estimate the FD of an image. This paper presents an efficient box-counting-based method for the improvement of FD estimation accuracy. A new model is proposed to assign the smallest number of boxes to cover the entire image surface at each selected scale as required, thereby yielding more accurate estimates. The experiments using synthesized fractional Brownian motion images, real texture images, and remote sensing images demonstrate this new method can outperform the well-known differential boxing-counting (DBC) method.     

Fast estimation of fractal dimension and correlation integral on stream data

In this paper we give a very space-efficient, yet fast method for estimating the fractal dimensionality of the points in a data stream. Algorithms to estimate the fractal dimension exist, such as the straightforward quadratic algorithm and the faster O(NlogN) or even O(N) box-counting algorithms. However, the sub-quadratic algorithms require Ω(N) space. In this paper, we propose an algorithm that computes the fractal dimension in a single pass, using a constant amount of memory relative to data cardinality. Experimental results on synthetic and real world data sets demonstrate the effectiveness of our algorithm.     

Finite fractal dimension of random attractor for stochastic non-autonomous strongly damped wave equation

In this paper, we first prove the existence of a random attractor for stochastic non-autonomous strongly damped wave equations with additive white noise. Then we apply a criteria to obtain an upper bound of fractal dimension of the random attractor of considered system.     

基于信息维数的复杂网络自相似性研究

描述了基于重构性的复杂网络自相似模型。在分形思想的基础上提出了复杂网络的自相似性研究,指出了分形思想中容量维数的不足,提出利用信息维数研究复杂网络的自相似性,这种方法更能客观反映网络的自相似性。给出了复杂网络自相似性测量方法和基于信息维数的仿真结果,数值仿真验证了理论分析的正确性。最后提出了进一步研究的方向。     

基于模块度的社交网络分形维度计算方法

社交网络是由个体或组织以及它们之间的关系所组成的社会结构。利用社交网络的分形结构来解释和预测社交网络的行为是目前的一个研究热点。分形维度是对社交网络中分形结构的度量,为了更准确地对社交网络分形结构进行度量,提出了一种基于模块度的盒子覆盖算法来计算分形维度。该算法利用分形维度和模块度互斥的性质,基于模块度最小的原则来构建盒子,再对盒子进行计数来计算社交网络的分形维度。仿真实验表明：基于模块度的盒子覆盖法比传统的盒覆盖算法得到更为精确的分形维度。     

A new version of Visual tool for estimating the fractal dimension of images

This work presents a new version of a Visual Basic 6.0 application for estimating the fractal dimension of images (Grossu et al., 2009 [1]). The earlier version was limited to bi-dimensional sets of points, stored in bitmap files. The application was extended for working also with comma separated values files and three-dimensional images.

New version program summary

Program title: Fractal Analysis v02Catalogue identifier: AEEG_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEEG_v2_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 9999No. of bytes in distributed program, including test data, etc.: 4 366 783Distribution format: tar.gzProgramming language: MS Visual Basic 6.0Computer: PCOperating system: MS Windows 98 or laterRAM: 30 MClassification: 14Catalogue identifier of previous version: AEEG_v1_0Journal reference of previous version: Comput. Phys. Comm. 180 (2009) 1999Does the new version supersede the previous version?: YesNature of problem: Estimating the fractal dimension of 2D and 3D images.Solution method: Optimized implementation of the box-counting algorithm.Reasons for new version:

1.

The previous version was limited to bitmap image files. The new application was extended in order to work with objects stored in comma separated values (csv) files. The main advantages are:

a)

Easier integration with other applications (csv is a widely used, simple text file format);

b)

Less resources consumed and improved performance (only the information of interest, the “black points”, are stored);

c)

Higher resolution (the points coordinates are loaded into Visual Basic double variables [2]);

d)

Possibility of storing three-dimensional objects (e.g. the 3D Sierpinski gasket).

2.

In this version the optimized box-counting algorithm [1] was extended to the three-dimensional case.

Summary of revisions:

1.

The application interface was changed from SDI (single document interface) to MDI (multi-document interface).

2.

One form was added in order to provide a graphical user interface for the new functionalities (fractal analysis of 2D and 3D images stored in csv files).

Additional comments: User friendly graphical interface; Easy deployment mechanism.Running time: In the first approximation, the algorithm is linear.References:

[1] I.V. Grossu, C. Besliu, M.V. Rusu, Al. Jipa, C.C. Bordeianu, D. Felea, Comput. Phys. Comm. 180 (2009)  1999-2001.

[2] F. Balena, Programming Microsoft Visual Basic 6.0, Microsoft Press, US, 1999.

     

复杂网络分形的盒维数改进算法

采用Welch Powell法对复杂网络分形的盒覆盖算法进行了改进,分析了改进算法的优越性、有效性,并对美国航空网（1997）和酵母蛋白质网进行了实验,揭示了两个复杂网络均具有分形特性。最后对这两个实际网络的分形含义进行了一定的解释。     

Heuristical top-k: fast estimation of centralities in complex networks

Centrality metrics have proven to be of a major interest when analyzing the structure of networks. Given modern-day network sizes, fast algorithms for estimating these metrics are needed. This paper proposes a computation framework (named Filter-Compute-Extract) that returns an estimate of the top-k most important nodes in a given network. We show that considerable savings in computation time can be achieved by first filtering the input network based on correlations between cheap and more costly centrality metrics. Running the costly metric on the smaller resulting filtered network yields significant gains in computation time. We examine the complexity improvement due to this heuristic for classic centrality measures, as well as experimental results on well-studied public networks.     

Analysing roughness of surface through fractal dimension: A review

In last three decades, fractal geometry (FG) has been the focus of attention by several researchers owing to it exhibiting excellent properties and robust application with respect to current research scenario. Fractal Dimension (FD) plays a vital role in order to analyse complex objects that are found in nature which was failed to be analysed by Euclidian geometry. FD is an imperative aspect of FG to provide indicative application in different areas of research including image processing, pattern recognition, computer graphics and many more. Analysis of an image is an important technique of image processing to describe image features like texture, roughness, smoothness etc., and is only possible through FG. Due to this reason many more technique were evolved to estimate the fractal dimension. The main aim of this article is to give a comprehensive review, which summarizes recent research progress on analysis of surface roughness and an overview of different concepts, and the way they work and their benefits and their limitations, and also we deliver how the different concepts taken into consideration to estimate FD depend upon different algorithms. This article also discusses several factors affecting FD estimation; types of similarity property, spatial resolution, sampling process, region of interest, spectral band and box-height criteria are discussed. Furthermore, we have tried to present the application area oriented versus core area of FG. There are several contradictory results found in many kinds of literature on the influence of different parameters while conducting FD analysis. Mainly it has been observed that the FD estimation will be affected by texture property, gray scale range, color property, color distance and the other parameters which are already mentioned. Hence this article will be beneficial for researchers in order to select precise FD estimation. However different algorithms lead to different results even with the use of the same kind of database images, so selection of appropriate technique is a major challenge for accurate estimation. Therefore an in-depth and proper understanding is required in order to choose the appropriate algorithm and also a robust algorithm for analysing roughness in better and precise way needs to be developed.     

The Generation of a Sort of Fractal Graphs

We present an approach for generating a sort of fractal graphs by a simple probabilistic logic neuron network and show that the graphs can be represented by a set of compressed codings.An algorithm for quickly finding the codings,i.e.,recognizing the corresponding graphs,is given.The codings are shown to be optimal.The results above possibly give us the clue for studying image compression and pattern recognition.     

基于三维盒维数算法的城市分维计算

通过将传统的二维盒维数算法扩展到三维空间,提出了一个基于三维空间的盒维数计算方法。分别利用三维盒维数算法和二维盒维数算法计算城市的分维,通过对计算结果进行比较分析,观察到城市空间结构在第三维同样具有分形特征,证明传统城市分维计算中采用基于二维空间的分维算法或者简单地利用二维分维加1的方法表示三维分维都是不准确的,并进而给出正确的城市分维计算方法。     

Derivation of the functional relations between fractal dimension of and shape indices of urban form

The relationships between the size, scale, shape, and dimension of urban settlements are basic problems remained to be further resolved, and this paper provides an available perspective for understanding these problems. Based on the standard circle, the relations between the fractal dimension of urban boundary and the compactness ratios of urban shape were derived from a geometric measure relation in a simple way. The compactness ratios proved to be the exponential functions of the reciprocal of the boundary dimension. The results can be generalized and applied to the common indices of shape including circularity ratio, ellipticity index, and form ratio, which are defined by urban area, perimeter, or Feret’s diameter. The mathematical models are empirically verified by the remote sensing data of China’s 31 mega-cities in 1990 and 2000 and lend support to the assumption that urban boundaries are pre-fractals rather than real fractals. A conclusion can be drawn that there exist certain functional relations between the shape indices and the boundary dimension, and within certain range of scales, the fractal parameters can be indirectly estimated by the ratios of size measurements to reflect the features of urban shapes.     

信号分形维数估计的研究与实现*

基于序列分形自仿射特性,提出一种实现一维信号分形维数估计的方法。按不同尺度将信号序列分段为映射区间和象区间,采用搜索算法确定与各象区间最优匹配的映射区间,并根据迭代函数系统理论估计信号的分形维数。以分形维数已知的MackeyGlass和Lorenz信号为例,仿真表明提出的方法能准确估计信号的分形维数,对实际应用具有一定的参考价值。