Dense subgraphs on dynamic networks

In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense substructures in otherwise sparse graphs (e.g. the World Wide Web or social networks); these might reveal community clusters or dense regions for possibly maintaining good communication infrastructure. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs that the member nodes are aware of. The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that (2 + e)-approximate the densest subgraph and (3 + e)-approximate the at-least-k-densest subgraph (for a given parameter k). Our algorithms work for a wide range of parameter values and run in O(D log n) time. Further, a special case of our results also gives the first fully decentralized approximation algorithms for densest and at-least-k-densest subgraph problems for static distributed graphs. © 2012 Springer-Verlag.

Brief announcement: Maintaining large dense subgraphs on dynamic networks

In distributed networks, some groups of nodes may have more inter-connections, perhaps due to their larger bandwidth availability or communication requirements. In many scenarios, it may be useful for the nodes to know if they form part of a dense subgraph, e.g., such a dense subgraph could form a high bandwidth backbone for the network. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs (subgraphs that the member nodes are aware of). The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model in the sense that only messages of O(log n) size are permitted, where n is the number of nodes in the network. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that approximate both the densest subgraph, i.e., the subgraph of the highest density in the network, and the at-least-k-densest subgraph (for a given parameter k), i.e., the densest subgraph of size at least k. We give a (2 + e)-approximation algorithm for the densest subgraph problem. The at-least-k-densest subgraph is known to be NP-hard for the general case in the centralized setting and the best known algorithm gives a 2-approximation. We present an algorithm that maintains a (3+e)-approximation in our distributed, dynamic setting. Our algorithms run in O(Dlog n) time. © 2012 Authors.

Non-convex dynamic economic/environmental dispatch with plug-in electric vehicle loads

Electric vehicles are a key prospect for future transportation. A large penetration of electric vehicles has the potential to reduce the global fossil fuel consumption and hence the greenhouse gas emissions and air pollution. However, the additional stochastic loads imposed by plug-in electric vehicles will possibly introduce significant changes to existing load profiles. In his paper, electric vehicles loads are integrated into an 5-unit system using a non-convex dynamic dispatch model. The actual infrastructure characteristics including valve-point effects, load balance constrains and transmission loss have been included in the model. Multiple load profiles are comparatively studied and compared in terms of economic and environmental impacts in order o identify patterns to charge properly. The study as expected shows ha off-peak charging is the best scenario with respect to using less fuels and producing less emissions.

The Effect of Illuminant Position on Perceived Curvature

In shaded scenes surface features can appear either concave or convex, depending upon the viewers judment about the direction of the prevailing illuminant. If other curvature cues are added to the image this ambiguity can be removed. However, it is not clear to what extent, if any, illuminant positin exerts an influence on the perceived magnitude of surface curvature. Subjects were presented with pairs of spherical surface patches in a curavture matching task. The patches were defined by shading and texture cues. The percevied curvature of a standard patch was measured as a function of light source position. We found a clear effect of light source position on apparent curvature. Perceived curvature decreased as light source tilt increased and as light source slant decreased. We also found that the strength of this effect is determined partly by a surface's reflectance function and partly by the relative weight of the texture cue. When a specular component was added to the stimuli, the effect of light source orientation was weakened. The weight of the texture cue was manipulated by disrupting the regular distribution of texture elements. We found an inverse relationship between the strength of the effecct and the weight of the texture cue: lowering the texture cue weight resulted in an enhancement of the illuminant position effect.

Is the General Public Licence a Rational Choice?

Open source projects are networks of developers, distributors and end-users of non-proprietary created knowledge goods. It has been argued that this form of organization has some advantages over the firm or market coordination. I show that for sufficiently convex and modular projects proprietary licences are not able to sustain sequential knowledge production which, however, can be carried out if the project is run on the open source basis.

Geometry in preduals of spaces of 2-homogeneous polynomials on Hilbert spaces

Let H be a (real or complex) Hilbert space. Using spectral theory and properties of the Schatten–Von Neumann operators, we prove that every symmetric tensor of unit norm in HoH is an infinite absolute convex combination of points of the form xox with x in the unit sphere of the Hilbert space. We use this to obtain explicit characterizations of the smooth points of the unit ball of HoH .

Completeness of certain function spaces

We give an example of a complete locally convex m-topology on the algebra of infinite differentiable functions on [0, 1] which is strictly coarser than the natural Frechet-topology but finer than the topology of pointwise convergence. A similar construction works on the algebra of continuous functions on [0, 1]. Using this examples we can separate different notions of diffotopy and homotopy.

On weak and strong Peano theorems

We say that the Peano theorem holds for a topological vector space $E$ if, for any continuous mapping $f : {\Bbb R}\times E \to E$ and any $(t(0), x(0))$ is an element of ${\Bbb R}\times E$, the Cauchy problem $\dot x(t) = f(t,x(t))$, $x(t(0)) = x(0)$, has a solution in some neighborhood of $t(0)$. We say that the weak version of Peano theorem holds for $E$ if, for any continuous map $f : {\Bbb R}\times E \to E$, the equation $\dot x(t) = f (t, x(t))$ has a solution on some interval. We construct an example (answering a question posed by S. G. Lobanov) of a Hausdorff locally convex topological vector space E for which the weak version of Peano theorem holds and the Peano theorem fails to hold. We also construct a Hausdorff locally convex topological vector space E for which the Peano theorem holds and any barrel in E is neither compact nor sequentially compact.

Gateaux complex differentiability and continuity

As is known, there are everywhere discontinuous infinitely Frechet differentiable functions on the real locally convex spaces D(R) and V(R) of finitely supported infinitely differentiable functions and, respectively, of generalized functions. In this paper the relationship between the complex differentiability and continuity of a function on a complex locally convex space is considered. We describe a class of complex locally convex spaces, which includes the complex space V(R), such that every Gateaux complex-differentiable function on a space of this class is continuous. We also describe another class of locally convex spaces, which includes the complex space D(R), such that on every space of this class there is an everywhere discontinuous infinitely Frechet complex-differentiable function whose derivatives are continuous.

On linear extension operators

We construct a countable-dimensional Hausdorff locally convex topological vector space $E$ and a stratifiable closed linear subspace $F$ subset of $E$ such that any linear extension operator from $C_b(F)$ to $C_b(E)$ is unbounded (here $C_b(X)$ stands for the Banach space of continuous bounded real-valued functions on $X$).

Model selection approaches for non-linear system identification: a review

The identification of non-linear systems using only observed finite datasets has become a mature research area over the last two decades. A class of linear-in-the-parameter models with universal approximation capabilities have been intensively studied and widely used due to the availability of many linear-learning algorithms and their inherent convergence conditions. This article presents a systematic overview of basic research on model selection approaches for linear-in-the-parameter models. One of the fundamental problems in non-linear system identification is to find the minimal model with the best model generalisation performance from observational data only. The important concepts in achieving good model generalisation used in various non-linear system-identification algorithms are first reviewed, including Bayesian parameter regularisation and models selective criteria based on the cross validation and experimental design. A significant advance in machine learning has been the development of the support vector machine as a means for identifying kernel models based on the structural risk minimisation principle. The developments on the convex optimisation-based model construction algorithms including the support vector regression algorithms are outlined. Input selection algorithms and on-line system identification algorithms are also included in this review. Finally, some industrial applications of non-linear models are discussed.

Unconditional constants and polynomial inequalities

If P is a polynomial on Rm of degree at most n then we define the polynomial |P|. Now if B is a convex compact set in Rm, we define the norm ||P||B of P as the maximum of P on B, and then we investigate the inequality || |P| ||B

Convergence of bimodules over maximal abelian selfadjoint algebras

We prove a continuity result for the map sending a masa-bimodule to its support. We characterise the convergence of a net of weakly closed convex hulls of bilattices in terms of the convergence of the corresponding supports, and establish a lower-semicontinuity result for the map sending a support to the corresponding masa-bimodule.

The level sets of the resolvent norm and convexity properties of Banach spaces

We construct a bounded linear operator on a separable, reflexive and strictly convex Banach space whose resolvent norm is constant in a neighbourhood of zero.

Nonlinear excitations in ferromagnetic chains with nearest and next nearest neighbor exchange interactions

Weakly nonlinear excitations in one-dimensional isotropic Heisenberg ferromagnetic chains with nearest- and next-nearest-neighbor exchange interactions are considered. Based on the properties of modulational stability of corresponding linear spin waves, the existence regions of bright and dark magnetic solitons of the system are discussed in the whole Brillouin zone. The antidark soliton mode which is convex soliton super-imposed with a plane wave component is obtained near the zero-dispersion points of the spin wave frequency spectrum. The analytical results are checked by numerical simulations. [S0163;1829(98)01838-4].