Heuristics for the Critical Node Detection Problem in Large Complex Networks

Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.

Generalized partition function zeros of 1D spin models and their critical behavior at edge singularities

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Critical points in logistic growth curves and treatment comparisons

Several biological phenomena have a behavior over time mathematically characterized by a strong increasing function in the early stages of development, then by a less pronounced growth, sometimes showing stability. The separation between these phases is very important to the researcher, since the maintenance of a less productive phase results in uneconomical activity. In this report we present methods of determining critical points in logistic functions that separate the early stages of growth from the asymptotic phase, with the aim of establishing a stopping critical point in the growth and on this basis determine differences in treatments. The logistic growth model is fitted to experimental data of imbibition of arariba seeds (Centrolobium tomentosum). To determine stopping critical points the following methods were used: i) accelerating growth function, ii) tangent at the inflection point, iii) segmented regression; iv) modified segmented regression; v) non-significant difference; and vi) non-significant difference by simulation. The analysis of variance of the abscissas and ordinates of the breakpoints was performed with the objective of comparing treatments and methods used to determine the critical points. The methods of segmented regression and of the tangent at the inflection point lead to early stopping points, in comparison with other methods, with proportions ordinate/asymptote lower than 0.90. The non-significant difference method by simulation had higher values of abscissas for stopping point, with an average proportion ordinate/asymptote equal to 0.986. An intermediate proportion of 0.908 was observed for the acceleration function method.

Pure spinor formalism as an N=2 topological string

Following suggestions of Nekrasov and Siegel, a non-minimal set of fields are added to the pure spinor formalism for the superstring. Twisted (c) over cap = 3 N = 2 generators are then constructed where the pure spinor BRST operator is the fermionic spin-one generator, and the formalism is interpreted as a critical topological string. Three applications of this topological string theory include the super-Poincare covariant computation of multiloop superstring amplitudes without picture-changing operators, the construction of a cubic open superstring field theory without contact-term problems, and a new four-dimensional version of the pure spinor formalism which computes F-terms in the spacetime action.

Statistical properties of a dissipative kicked system: Critical exponents and scaling invariance

A new universal empirical function that depends on a single critical exponent (acceleration exponent) is proposed to describe the scaling behavior in a dissipative kicked rotator. The scaling formalism is used to describe two regimes of dissipation: (i) strong dissipation and (ii) weak dissipation. For case (i) the model exhibits a route to chaos known as period doubling and the Feigenbaum constant along the bifurcations is obtained. When weak dissipation is considered the average action as well as its standard deviation are described using scaling arguments with critical exponents. The universal empirical function describes remarkably well a phase transition from limited to unlimited growth of the average action. (C) 2012 Elsevier B.V. All rights reserved.

Critical exponents for a transition from integrability to non-integrability via localization of invariant tori in the Hamiltonian system

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Relaxation-chaos phenomena in celestial mechanics. I. On wisdom's model for the 3/1 kirkwood gap

Sudden eccentricity increases of asteroidal motion in 3/1 resonance with Jupiter were discovered and explained by J. Wisdom through the occurrence of jumps in the action corresponding to the critical angle (resonant combination of the mean motions). We pursue some aspects of this mechanism, which could be termed relaxation-chaos: that is, an unconventional form of homoclinic behavior arising in perturbed integrable Hamiltonian systems for which the KAM theorem hypothesis do not hold. © 1987.

Interference phenomena, chiral bosons, and Lorentz invariance

We have studied the theory of gauged chiral bosons and proposed a general theory, a master action, that encompasses different kinds of gauge field couplings in chiral bosonized theories with first-class chiral constraints. We have fused opposite chiral aspects of this master action using the soldering formalism and applied the final action to several well-known models. The Lorentz rotation permitted us to fix conditions on the parameters of this general theory in order to preserve the relativistic invariance. We also have established some conditions on the arbitrary parameter concerned in a chiral Schwinger model with a generalized constraint, investigating both covariance and Lorentz invariance. The results obtained supplement the one that shows the soldering formalism as a new method of mass generation. ©2001 The American Physical Society.

Critical numbers of attractive Bose-Einstein condensed atoms in asymmetric traps

A quantitative analysis of the critical number of attractive Bose-Einstein condensed atoms in asymmetric traps was studied. The Gross-Pitaevskii (GP) formalism for an atomic system with arbitrary nonspherically symmetric harmonic trap was also discussed. Characteristic limits were obtained for reductions from three to two and one dimensions from three to two and one dimensions, in perfect cylindrical symmetries as well as in deformed ones.

Pure spinor formalism as an N ≤ 2 topological string

Following suggestions of Nekrasov and Siegel, a non-minimal set of fields are added to the pure spinor formalism for the superstring. Twisted ĉ ≤ 3 N ≤ 2 generators are then constructed where the pure spinor BRST operator is the fermionic spin-one generator, and the formalism is interpreted as a critical topological string. Three applications of this topological string theory include the super-Poincaré covariant computation of multiloop superstring amplitudes without picture-changing operators, the construction of a cubic open superstring field theory without contact-term problems, and a new four-dimensional version of the pure spinor formalism which computes F-terms in the spacetime action. © SISSA 2005.

Inverted critical adsorption of polyelectrolytes in confinement

What are the fundamental laws for the adsorption of charged polymers onto oppositely charged surfaces, for convex, planar, and concave geometries? This question is at the heart of surface coating applications, various complex formation phenomena, as well as in the context of cellular and viral biophysics. It has been a long-standing challenge in theoretical polymer physics; for realistic systems the quantitative understanding is however often achievable only by computer simulations. In this study, we present the findings of such extensive Monte-Carlo in silico experiments for polymer-surface adsorption in confined domains. We study the inverted critical adsorption of finite-length polyelectrolytes in three fundamental geometries: planar slit, cylindrical pore, and spherical cavity. The scaling relations extracted from simulations for the critical surface charge density sigma(c)-defining the adsorption-desorption transition-are in excellent agreement with our analytical calculations based on the ground-state analysis of the Edwards equation. In particular, we confirm the magnitude and scaling of sigma(c) for the concave interfaces versus the Debye screening length 1/kappa and the extent of confinement a for these three interfaces for small kappa a values. For large kappa a the critical adsorption condition approaches the known planar limit. The transition between the two regimes takes place when the radius of surface curvature or half of the slit thickness a is of the order of 1/kappa. We also rationalize how sigma(c)(kappa) dependence gets modified for semi-flexible versus flexible chains under external confinement. We examine the implications of the chain length for critical adsorption-the effect often hard to tackle theoretically-putting an emphasis on polymers inside attractive spherical cavities. The applications of our findings to some biological systems are discussed, for instance the adsorption of nucleic acids onto the inner surfaces of cylindrical and spherical viral capsids.

Dynamics, rheology and critical properties of colloidal fluid mixtures

Liquids under the influence of external fields exhibit a wide range of intriguing phenomena that can be markedly different from the behaviour of a quiescent system. This work considers two different systems — a glassforming Yukawa system and a colloid-polymer mixture — by Molecular Dynamics (MD) computer simulations coupled to dissipative particle dynamics. The former consists of a 50-50 binary mixture of differently-sized, like-charged colloids interacting via a screened Coulomb (Yukawa) potential. Near the glass transition the influence of an external shear field is studied. In particular, the transition from elastic response to plastic flow is of interest. At first, this model is characterised in equilibrium. Upon decreasing temperature it exhibits the typical dynamics of glassforming liquids, i.e. the structural relaxation time τα grows strongly in a rather small temperature range. This is discussed with respect to the mode-coupling theory of the glass transition (MCT). For the simulation of bulk systems under shear, Lees-Edwards boundary conditions are applied. At constant shear rates γ˙ ≫ 1/τα the relevant time scale is given by 1/γ˙ and the system shows shear thinning behaviour. In order to understand the pronounced differences between a quiescent system and a system under shear, the response to a suddenly commencing or terminating shear flow is studied. After the switch-on of the shear field the shear stress shows an overshoot, marking the transition from elastic to plastic deformation, which is connected to a super-diffusive increase of the mean squared displacement. Since the average static structure only depends on the value of the shear stress, it does not discriminate between those two regimes. The distribution of local stresses, in contrast, becomes broader as soon as the system starts flowing. After a switch-off of the shear field, these additional fluctuations are responsible for the fast decay of stresses, which occurs on a time scale 1/γ˙ . The stress decay after a switch-off in the elastic regime, on the other hand, happens on the much larger time scale of structural relaxation τα. While stresses decrease to zero after a switch-off for temperatures above the glass transition, they decay to a finite value for lower temperatures. The obtained results are important for advancing new theoretical approaches in the framework of mode-coupling theory. Furthermore, they suggest new experimental investigations on colloidal systems. The colloid-polymer mixture is studied in the context of the behaviour near the critical point of phase separation. For the MD simulations a new effective model with soft interaction potentials is introduced and its phase diagram is presented. Here, mainly the equilibrium properties of this model are characterised. While the self-diffusion constants of colloids and polymers do not change strongly when the critical point is approached, critical slowing down of interdiffusion is observed. The order parameter fluctuations can be determined through the long-wavelength limit of static structure factors. For this strongly asymmetric mixture it is shown how the relevant structure factor can be extracted by a diagonalisation of a matrix that contains the partial static structure factors. By presenting first results of this model under shear it is demonstrated that it is suitable for non-equilibrium simulations as well.

Partial Discharge Phenomena in Converter and Traction Transformers: Identification and Reliability

After the development of power electronics converters, the number of transformers subjected to non-sinusoidal stresses (including DC) has increased in applications such as HVDC links and traction (electric train power cars). The effects of non-sinusoidal voltages on transformer insulation have been investigated by many researchers, but still now, there are some issues that must be understood. Some of those issues are tackled in this Thesis, studying PD phenomena behavior in Kraft paper, pressboard and mineral oil at different voltage conditions like AC, DC, AC+DC, notched AC and square waveforms. From the point of view of converter transformers, it was found that the combined effect of AC and DC voltages produces higher stresses in the pressboard that those that are present under pure DC voltages. The electrical conductivity of the dielectric systems in DC and AC+DC conditions has demonstrated to be a critical parameter, so, its measurement and analysis was also taken into account during all the experiments. Regarding notched voltages, the RMS reduction caused by notches (depending on firing and overlap angles) seems to increase the PDIV. However, the experimental results show that once PD activity has incepted, the notches increase PD repetition rate and magnitude, producing a higher degradation rate of paper. On the other hand, the reduction of mineral oil stocks, their relatively low flash point as well as environmental issues, are factors that are pushing towards the use of esters as transformer insulating fluids. This PhD Thesis also covers the study of two different esters with the scope to validate their use in traction transformers. Mineral oil was used as benchmark. The complete set of dielectric tests performed in the three fluids, show that esters behave better than mineral oil in practically all the investigated conditions, so, their application in traction transformers is possible and encouraged.

Interacting quantum-dissipative tunnelling systems

Die Untersuchung von dissipativen Quantensystemen erm¨oglicht es, Quantenph¨anomene auch auf makroskopischen L¨angenskalen zu beobachten. Das in dieser Dissertation gew¨ahlte mikroskopische Modell erlaubt es, den bisher nur ph¨anomenologisch zug¨anglichen Effekt der Quantendissipation mathematisch und physikalisch herzuleiten und zu untersuchen. Bei dem betrachteten mikroskopischen Modell handelt es sich um eine 1-dimensionale Kette von harmonischen Freiheitsgraden, die sowohl untereinander als auch an r anharmonische Freiheitsgrade gekoppelt sind. Die F¨alle einer, respektive zwei anharmonischer Bindungen werden in dieser Arbeit explizit betrachtet. Hierf¨ur wird eine analytische Trennung der harmonischen von den anharmonischen Freiheitsgraden auf zwei verschiedenen Wegen durchgef¨uhrt. Das anharmonische Potential wird als symmetrisches Doppelmuldenpotential gew¨ahlt, welches mit Hilfe der Wick Rotation die Berechnung der ¨Uberg¨ange zwischen beiden Minima erlaubt. Das Eliminieren der harmonischen Freiheitsgrade erfolgt mit Hilfe des wohlbekannten Feynman-Vernon Pfadintegral-Formalismus [21]. In dieser Arbeit wird zuerst die Positionsabh¨angigkeit einer anharmonischen Bindung im Tunnelverhalten untersucht. F¨ur den Fall einer fernab von den R¨andern lokalisierten anharmonischen Bindung wird ein Ohmsches dissipatives Tunneln gefunden, was bei der Temperatur T = 0 zu einem Phasen¨ubergang in Abh¨angigkeit einer kritischen Kopplungskonstanten Ccrit f¨uhrt. Dieser Phasen¨ubergang wurde bereits in rein ph¨anomenologisches Modellen mit Ohmscher Dissipation durch das Abbilden des Systems auf das Ising-Modell [26] erkl¨art. Wenn die anharmonische Bindung jedoch an einem der R¨ander der makroskopisch grossen Kette liegt, tritt nach einer vom Abstand der beiden anharmonischen Bindungen abh¨angigen Zeit tD ein ¨Ubergang von Ohmscher zu super- Ohmscher Dissipation auf, welche im Kern KM(τ ) klar sichtbar ist. F¨ur zwei anharmonische Bindungen spielt deren indirekteWechselwirkung eine entscheidende Rolle. Es wird gezeigt, dass der Abstand D beider Bindungen und die Wahl des Anfangs- und Endzustandes die Dissipation bestimmt. Unter der Annahme, dass beide anharmonischen Bindung gleichzeitig tunneln, wird eine Tunnelwahrscheinlichkeit p(t) analog zu [14], jedoch f¨ur zwei anharmonische Bindungen, berechnet. Als Resultat erhalten wir entweder Ohmsche Dissipation f¨ur den Fall, dass beide anharmonischen Bindungen ihre Gesamtl¨ange ¨andern, oder super-Ohmsche Dissipation, wenn beide anharmonischen Bindungen durch das Tunneln ihre Gesamtl¨ange nicht ¨andern.

Tolerance and Critical Thinking

Post-soviet countries are in the process of transformation from a totalitarian order to a democratic one, a transformation which is impossible without a profound shift in people's way of thinking. The group set themselves the task of determining the essence of this shift. Using a multidisciplinary approach, they looked at concrete ways of overcoming the totalitarian mentality and forming that necessary for an open democratic society. They studied the contemporary conceptions of tolerance and critical thinking and looked for new foundations of criticism, especially in hermeneutics. They then sought to substantiate the complementary relation between tolerance and criticism in the democratic way of thinking and to prepare a a syllabus for teaching on the subject in Ukrainian higher education. In a philosophical exploration of tolerance they began with relgious tolerance as its first and most important form. Political and social interests often lay at the foundations of religious intolerance and this implicitly comprised the transition to religious tolerance when conditions changed. Early polytheism was more or less indifferent to dogmatic deviations but monotheism is intolerant of heresies. The damage wrought by the religious wars of the Reformations transformed tolerance into a value. They did not create religious tolerance but forced its recognition as a positive phenomenon. With the weakening of religious institutions in the modern era, the purely political nature of many conflicts became evident and this stimulated the extrapolation of tolerance into secular life. Each historical era has certain acts and operations which may be interpreted as tolerant and these can be classified as to whether or not they are based on the conscious following of the principle of tolerance. This criterion requires the separation of the phenomenon of tolerance from its concept and from tolerance as a value. Only the conjunction of a concept of tolerance with a recognition of its value can transform it into a principle dictating a norm of conscious behaviour. The analysis of the contemporary conception of tolerance focused on the diversity of the concept and concluded that the notions used cannot be combined in the framework of a single more or less simple classification, as the distinctions between them are stimulated by the complexity of the realty considered and the variety of its manifestations. Notions considered in relation to tolerance included pluralism, respect and particular-universal. The rationale of tolerance was also investigated and the group felt that any substantiation of the principle of tolerance must take into account human beings' desire for knowledge. Before respecting or being tolerant of another person different from myself, I should first know where the difference lies, so knowledge is a necessary condition of tolerance.The traditional division of truth into scientific (objective and unique) and religious, moral, political (subjective and so multiple) intensifies the problem of the relationship between truth and tolerance. Science was long seen as a field of "natural" intolerance whereas the validity of tolerance was accepted in other intellectual fields. As tolerance eemrges when there is difference and opposition, it is essentially linked with rivaly and there is a a growing recognition today that unlimited rivalry is neither able to direct the process of development nor to act as creative matter. Social and economic reality has led to rivalry being regulated by the state and a natural requirement of this is to associate tolerance with a special "purified" form of rivalry, an acceptance of the actiivity of different subjects and a specification of the norms of their competition. Tolerance and rivalry should therefore be subordinate to a degree of discipline and the group point out that discipline, including self-discipline, is a regulator of the balance between them. Two problematic aspects of tolerance were identified: why something traditionally supposed to have no positive content has become a human activity today, and whether tolerance has full-scale cultural significance. The resolution of these questions requires a revision of the phenomenon and conception of tolerance to clarify its immanent positive content. This involved an investigation of the contemporary concept of tolerance and of the epistemological foundations of a negative solution of tolerance in Greek thought. An original soution to the problem of the extrapolation of tolerance to scientific knowledge was proposed based on the Duhem-Quine theses and conceptiion of background knowledge. In this way tolerance as a principle of mutual relations between different scientific positions gains an essential epistemological rationale and so an important argument for its own universal status. The group then went on to consider the ontological foundations for a positive solution of this problem, beginning with the work of Poincare and Reichenbach. The next aspect considered was the conceptual foundations of critical thinking, looking at the ideas of Karl Popper and St. Augustine and at the problem of the demarcation line between reasonable criticism and apologetic reasoning. Dogmatic and critical thinking in a political context were also considered, before an investigation of critical thinking's foundations. As logic is essential to critical thinking, the state of this discipline in Ukrainian and Russian higher education was assessed, together with the limits of formal-logical grounds for criticism, the role of informal logical as a basis for critical thinking today, dialectical logic as a foundation for critical thinking and the universality of the contemporary demand for criticism. The search for new foundations of critical thinking covered deconstructivism and critical hermeneutics, including the problem of the author. The relationship between tolerance and criticism was traced from the ancient world, both eastern and Greek, through the transitional community of the Renaissance to the industrial community (Locke and Mill) and the evolution of this relationship today when these are viewed not as moral virtues but as ordinary norms. Tolerance and criticism were discussed as complementary manifestations of human freedom. If the completeness of freedom were accepted it would be impossible to avoid recognition of the natural and legal nature of these manifestations and the group argue that critical tolerance is able to avoid dismissing such negative phenomena as the degradation of taste and manner, pornography, etc. On the basis of their work, the group drew up the syllabus of a course in "Logic with Elements of Critical Thinking, and of a special course on the "Problem of Tolerance".