Search

Scale-free networks are usually defined as the ones that have power-law degree distributions. Since many of real world networks such as the World Wide Web, the Internet, citation networks, biological networks, and so on, have this property in common, scale-free networks have attracted interests of researchers so far. They also revealed that such networks have some typical properties such as high cluster coefficient and small diameter as well, and a lot of network models have been proposed to explain them. Recently, some new observations for a real world network are reported [12]. It tries to find a special kind of cliques from a network and introduces observations; 1. the size distributions of cliques show a power-law, 2. the degree distribution of the network after contracting those cliques show a power-law, and 3. by regarding the contracted network as the original, 1 and 2 are observed repeatedly. In this paper, we propose a new network model constructed by a `clique expansion΄ procedure, to explain these new hierarchical structure of cliques. [ABSTRACT FROM AUTHOR]

Scale free graphs have attracted attention by their non-uniform structure that can be used as a model for various social and physical networks. In this paper, we propose a natural and simple random model for generating scale free interval graphs. The model generates a set of intervals randomly, which defines a random interval graph. The main advantage of the model is its simpleness. The structure/properties of the generated graphs are analyzable by relatively simple probabilistic and/or combinatorial arguments, which is different from the most of the other models for which we need to approximate the processes by certain differential equations. We indeed show that the distribution of degrees follows power law, and it achieves large cluster coefficient. [ABSTRACT FROM AUTHOR]

For a phylogeny reconstruction problem, Desper and Gascuel [2] proposed Greedy Minimum Evolution algorithm (in short, GME) and Balanced Minimum Evolution algorithm (in short, BME). Both of them are faster than the current major algorithm, Neighbor Joining (in short, NJ); however, less accurate when an input distance matrix has errors. In this paper, we prove that BME has the same optimal robustness to such errors as NJ but GME does not. Precisely, we prove that if the maximum distance error is less than a half of the minimum edge length of the target tree, then BME reconstruct it correctly. On the other hand, there is some distance matrix such that maximum distance error is less than $\frac{2}{\sqrt{n}}$ of the minimum edge length of the target tree, for which GME fails to reconstruct the target tree. [ABSTRACT FROM AUTHOR]