Boltzmann-Shannon interaction entropy: A normalized measure for continuous variables with an application as a subsample quality metric.

The recent introduction of geometric partition entropy offered an alternative to differential Shannon entropy for the quantification of uncertainty as estimated from a sample drawn from a one-dimensional bounded continuous probability distribution. In addition to being a fresh perspective for the basis of continuous information theory, this new approach provided several improvements over traditional entropy estimators including its effectiveness on sparse samples and a proper incorporation of the impact from extreme outliers. However, a complimentary relationship exists between the new geometric approach and the basic form of its frequency-based predecessor that is leveraged here to define an entropy measure with no bias toward the sample size. This stable normalized measure is named the Boltzmann-Shannon interaction entropy (BSIE)) as it is defined in terms of a standard divergence between the measure-based and frequency-based distributions that can be associated with the two historical figures. This parameter-free measure can be accurately estimated in a computationally efficient manner, and we illustrate its utility as a quality metric for subsampling in the context of nonlinear polynomial regression.

Spanning trees of recursive scale-free graphs.

We present a link-by-link rule-based method for constructing all members of the ensemble of spanning trees for any recursively generated, finitely articulated graph, such as the Dorogovtsev-Goltsev-Mendes (DGM) net. The recursions allow for many large-scale properties of the ensemble of spanning trees to be analytically solved exactly. We show how a judicious application of the prescribed growth rules selects for certain subsets of the spanning trees with particular desired properties (small world, extended diameter, degree distribution, etc.), and thus approximates and/or provides solutions to several optimization problems on undirected and unweighted networks. The analysis of spanning trees enhances the usefulness of recursive graphs as sophisticated models for everyday life complex networks.

The essential synchronization backbone problem.

Network optimization strategies for the process of synchronization have generally focused on the re-wiring or re-weighting of links in order to (1) expand the range of coupling strengths that achieve synchronization, (2) expand the basin of attraction for the synchronization manifold, or (3) lower the average time to synchronization. A new optimization goal is proposed in seeking the minimum subset of the edge set of the original network that enables the same essential ability to synchronize in that the synchronization manifolds have conjugate stability. We call this type of minimal spanning subgraph an essential synchronization backbone of the original system, and we present two algorithms: one is a strategy for an exhaustive search for a true solution, while the other is a method of approximation for this combinatorial problem. The solution spaces that result from different choices of dynamical systems and coupling schemes vary with the level of a hierarchical structure present and also the number of interwoven central cycles. Applications can include the important problem in civil engineering of power grid hardening, where new link creation may be costly, and the defense of certain key links to the functional process may be prioritized.

Stochastic and mixed flower graphs.

Stochasticity is introduced to a well studied class of recursively grown graphs: (u,v)-flower nets, which have power-law degree distributions as well as small-world properties (when u=1). The stochastic variant interpolates between different (deterministic) flower graphs thus adding flexibility to the model. The random multiplicative growth process involved, however, leads to a spread ensemble of networks with finite variance for the number of links, nodes, and loops. Nevertheless, the degree exponent and loopiness exponent attain unique values in the thermodynamic limit of infinitely large graphs. We also study a class of mixed flower networks, closely related to the stochastic flowers, but which are grown recursively in a deterministic way. The deterministic growth of mixed flower-nets eliminates ensemble spreads, and their recursive growth allows for exact analysis of their (uniquely defined) mixed properties.