Second International Conference in Network Analysis 2.
Second International Conference on
Network Analysis 2012
May 7th –May 9th, 2012
Center for Applied optimization (CAO),
University of Florida, USA
Laboratory of Algorithms and Technologies for Networks Analysis
(LATNA), Higher School of Economics, Russia
Monday, May7th
Room 313HSE, 25/12BolshayaPecherskayaStr.
15:00-15:30 Panos M. Pardalos
Second International Conference on Network Analysis 2012
15:30-16:20 Christodoulos A. Floudas
Towards Large Scale Deterministic Global Optimization
16:20-16:40 Coffee Break
16:40-18:10 Session 1
LudmilaEgorova
Behavioral model of stock exchange
Dmitry Malyshev
On expanding operators for the independent set problem
Dmitry Mokeev
Structural and complexial properties of P3-könig graphs
Victor Zamaraev
A heuristics for the weighted independent set problem
Tuesday, May8th
Room 313HSE, 25/12 BolshayaPecherskaya Str.
10:00-10:50 Boris Mirkin
Representing Activities by Taxonomy Concepts: Clustering and Lifting
10:50-11:10 Coffee Break
11:10-12:30 Session 1
Pando G. Georgiev
Innovative tools for analyzing state transitions and evolution of complex dynamic networks
Alexey Yashunsky
Using Online Social Networks for Social Geography Studies
Alexander Rubchinsky
A New Algorithm of Network Decomposition and its Application for Stock Market Analysis
12:30-14:00 Lunch Break
14:00-14:50 Ding-Zhu Du
Min-Weight Connected Sensor Cover and Max-Lifetime Target Coverage
14:50-15:50 Session 2
Anton Kocheturov
Market Graph Analysis by Means of the P-Median Problem
Mikhail Batsyn
Applying Tolerances to the Asymmetric Capacitated Vehicle Routing Problem
Evgeny Maslov
Complex approach to solving the maximum clique problem
15:50-16:10 Coffee Break
16:10-17:30 Session 3
Grigory Bautin
Markov chains in modeling of the Russian financial market
Dmitry Gorbunov
Simulation of Pedestrian Crowds with Anticipation using Cellular Automata Approach
Pankaj Kumar
Behavioural Dynamics in Stock Market
LazarevEvgenyAlexandrovich
Bi-criteria model and algorithms of solving data transmission network optimization problem
Wednesday, May9th
Room 313HSE, 25/12 BolshayaPecherskaya Str.
9:30-10:20 Mauricio G. C. Resende
Randomized Algorithms for the Handover Minimization Problem in Wireless Network Design
10:20-10:40 Coffee Break
10:40-12:20 Session 1
D.V. Kasatkin
Synaptic cellular automaton for description the sequential dynamics of excitatory neural networks
Pavel Sukhov
Heuristic Algorithm for the Single Machine Scheduling Problem
Ilya Bychkov
“Patterns” for solving the Cell Formation Problem
Peter Koldanov
Statistical Properties of the Market Graph
12:30-14:00 Lunch Break
Towards Large Scale Deterministic Global Optimization
Christodoulos A. Floudas
Department of Chemical and Biological Engineering
Princeton University, USA
In this seminar, we will provide an overview of the research progress in deterministic global optimization. The focus will be on important contributions during the last five years, and will provide a perspective for future research opportunities. The overview will cover the areas of (a) twice continuously differentiable constrained nonlinear optimization, and (b) mixed-integer nonlinear optimization models. Subsequently, we will present our recent fundamental advances in (i) convex envelope results for multi-linear functions, and edge concave functions, (ii) a piecewise quadratic convex underestimator for twice continuously differentiable functions, (iii) piecewise linear relaxations of bilinear functions, (iv) large scale extended pooling problems, and (v) large scale generalized pooling problems. Computational studies on medium and large scale global optimization applications will illustrate the potential of these advances.
Behavioral model of stock exchange
FuadAleskerov, Lyudmila Egorova
National Research University Higher School of Economics, Moscow, Russia
,
Due to the global financial crisis and its consequences stock exchange nowadays is an essential element of market infrastructure, a sensitive "barometer" to the slightest changes in the economy. For this reason the importance of the study of the stock exchange processes and the construction of adequate models of the exchange game has been increased. Behavioral finance is a new direction in financial economics, which explains the trading process based on investor psychology and the impact of their behavior on the market. Recently Taleb N.N. suggested to analyze the crises (called Black Swans) as the events with three main properties. A Black Swan is a very rare event, it carries an extreme impact, and the occurrence of this event cannot be predicted in advance (and only after the Black Swan happened we can come up with its explanation). Thus, the Black Swan is a metaphor for the crisis itself. Therefore everyone has to expect these Black Swans and be ready for their occurrence. However, should all investors follow such a strategy? And should we expect a rare and unpredictable event, even with a big impact, rather than deal with “the bird in the hand”?
To answer this question we construct a mathematical model of the stock exchange, in which the processes are modeled as a reaction to the signals about the state of the economy. There are two Poisson flows of signals/events of two types, one of which is 'regular' event that corresponds to a stable economy and the second one is the 'crisis' event signaling about the crisis. The intensity of the first flow is much greater than the intensity of the crisis events (Black Swans rarity condition). The player does not know in advance about the type of the incoming signal and have to recognize it (the condition of unpredictability). Player’s wealth depends on how well she identifies the signals on the stock exchange, because gain/loss from the crisis event is much greater than the gain/loss in case of the ordinary, frequent events (condition of great influence).
We showed that the average player's gain will be positive if she can correctly recognize the ordinary events in slightly more than in the half of the cases. In other words, players do not need to play more sophisticated games, trying to identify crises events in advance. This conclusion resembles the logic of precautionary behavior, that prescripts to play the game with almost reliable small wins. We believe that this very phenomenon lies in the basis of unwillingness of people to expect crises permanently and to try recognizing them. The proposed model was tested on stock exchange indices (S&P 500, Dow Jones, САС 40, DAX, Nikkei 225, Hang Seng, on time interval 1999-2009) and on data of different shares (Microsoft, General Electric, Morgan Chase, Proctor&Gamble, Johnson&Johnson, Apple, AT&T, IBM, Bank of America).
Acknowledgement. We are grateful for partial financial support of the HSE International Laboratory of Decision Choice and Analysis (DeCAn Lab) and NRU HSE Science Foundation (grant № 10-04-0030). Lyudmila Egorova expresses sincere gratitude to the HSE Laboratory of Algorithms and Technologies for Networks Analysis (LATNA) for partial financial support.
On expanding operators for the independent set problem
Malyshev Dmitry Sergeevich
National Research University Higher School of Economics,
National Research University Lobachevky State University of Nizhniy Novgorod, Russia
All considered graphs are simple, i.e. undirected unlabeled graph without loops and multiple edges. A class of graphs is a set of simple graphs. A class of graphs is called hereditary if it is closed under deletions of vertices. It is known that a hereditary (and only hereditary class) can be defined by a set of its forbidden induced subgraphs, i.e. graphs that don't belong to . It is denoted by.
Let be an NP-complete graph problem. A hereditary graph class is called -easyif is polynomial-time solvable for graphs in. All known to the author proofs of papers on expansions of cases with polynomial-time solvability substantially use a specific character of the old, narrower case. At the same time, it would be desirable to have «universal» such kind generalizations. For the family of hereditary graph classes it is offered to consider transformations (one- or many-variable function with arguments in a part of ), such that and from -easiness of follows that is also -easy. We will refer such kind transformations to -expanding operators.
The case, when is the independent set problem and , will be only considered further. The interest in hereditary subclasses of is conditioned by several causes. Firstly, if , then the independent set problem is polynomial-time solvable in if and only if is a forest. Moreover, the case is unique among all connected graphs with five vertices with open computational status of the problem for . There are many papers in which one or more forbidden induced subgraphs are added to and the effective solvability of the problem for obtained graphs class is proved. Secondly, for any graph with at most five vertices, and , the problem admits a polynomial-time algorithm for graphs in . Unfortunately, its complexity is unknown for the class .
Two concrete expanding operators for the independent set problem will be specified further. The product of and is the graph . It is easy to see that the mapping is an expanding operator for the problem. Two more such operators are described below.
Theorem. The mapping is an expanding operator for the independent set problem. For any naturalthe mapping is an expanding operator for the independent set problem.
The author is partially supported byLATNALaboratory, NRU HSE, RF government grant, ag.11.G34.31.0057, by Russian Foundation for Basic Research, grants 11-01-00107-аи 12-01-00749-а, and by Federal Target Program «Academic and educational specialists of innovative Russia», state contract 16.740.11.0310
Structural and complexial properties of P3-könig graphs
D. B.Mokeev
National Research University Lobachevky State University of Nizhniy Novgorod, Russia
Hereditary class of graphs in which maximum number of non-intersecting P3-subgraphs is equal with minimum number of vertexes contains in every such subgraphs and polynomial recognition algorithm for this class are described.
A heuristics for the weighted independent set problem
B.I. Goldengorin1, D.S. Malyshev1,2, P.M. Pardalos1,3, V.A. Zamaraev1,2
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhniy Novgorod, Russia
2National Research University Lobachevky State University of Nizhniy Novgorod, Russia
3Center for Applied Optimization, University of Florida, Gainesville, USA
, , ,
In this paper we design a new heuristic tolerance-based algorithm for solving the Weighted Independent Set problem (the WIS, for short). Our algorithm is based on the polynomially solvable special case of the WIS, which is defined on trees (the WIST, for short). We show that an optimal solution and all tolerances with respect to this solution of the WIST might be simultaneously found by the adjusted Chen et al. dynamic programming algorithm in O(n) time. Based on this procedure we offer a heuristic algorithm for the WIS, which takes O(mnlog(m)) time. We also present several computational experiments for its approximation ratio, they showed good enough results for some models of sparse graphs.
The authors is partially supported by LATNA Laboratory, NRU HSE, RF government grant, ag. 11.G34.31.0057. This study comprises research findings from the ‘Calculus of tolerances in combinatorial optimization problems: theory and algorithms’ Project carried out within The Higher School of Economics’ 2012 Academic Fund Program.
Representing Activities by Taxonomy Concepts: Clustering and Lifting
Boris Mirkin
National Research University Higher School of Economics, Moscow RF
Birkbeck University of London, London UK
Given a taxonomy of a domain, the activities of an organization in the domain can be represented by crisp or fuzzy clusters of the corresponding taxonomy leaf concepts(thematic clusters). To represent a thematic cluster in the taxonomy, a parsimoniouslifting method is developed. The method maps the cluster’s topics to higher ranks of thetaxonomy tree. The lifting criterion involves a penalty function summing penalties for the "head" subjects together with penalties for emerging gaps and offshoots. The developments areillustrated by using synthetic and real-world data.
Innovative tools for analyzing state transitions and evolution of complex dynamic networks
Pando G. Georgiev and Panos M. Pardalos
Center for Applied Optimization
University of Florida, Gainesville, USA
,
The problem of detection and prediction of changes (state transitions), dependencesand causalities in the evolution of complex networks is of tremendous significance.Several important practical networks desperately need tools for prediction, for instance: in biological networks - epileptic brain networks for prediction of epileptic seizures;inpower system networks - electric grid, for prediction of blackouts; in social networks -for prediction of malicious behaviors of some social groups, etc.
We present several innovative tools applicable to this problem:
1) Reproducing Kernel Banach Spaces.
We extend the idea of Reproducing Kernel Hilbert Spaces to Banach spaces (and beyond),developing a theory without the requirement of existence of semi-inner product(whichrequirement is already explored in another construction of RKBS). We applyour construction to the basic learning algorithms, including support vector machines,kernel regression, kernel principal component analysis. We demonstrate the betteradaptive features of such spaces to new dimensionality reduction techniques and to detection of state transitions in some complex networks, as epileptic brain. We introducea qualitative new concept ”multiple reproducing kernels”, which encompasses not onlybivariate, but also multivariate connections between data variables, arranging them ina kernel tensor - a generalization of the kernel matrix.
2) Tensor decompositions.
Multi-way structures of the data has been widely ignored in many fields of research,especially in dynamical complex networks. The functional MRI is another typicalexample, where the data is inheritably tensorial. Collapsing some of the modes to formof a matrix or vector leads to loss of information. Many tensor representations admituniqueness of the decomposition without additional constraints such as orthogonality(as in Singular value decomposition, or PCA) or independence (as in IndependentComponent Analysis). We review some tensor decomposition methods and introducenew ones, involving sparsity, suitable for complex sparse networks.
3) Adaptive multi-class learning problems.
We generalize the main task of statistical learning theory to multiclass learningproblems, allowing several classes approximating functions to choose adaptively fromseveral classes of data (possibly heterogeneous).
4) Nonlinear skeletons of data sets and skeleton classifiers.
A particular case of multiclass learning problems is the problem of subspace clustering, which we extend to RKBS defining in such a way the concept of nonlinearskeletons and its derivative, Skeleton Classifier.
5) Trajectory reconstruction.
Square roots, or more generally, iterative roots of operators are of interest in dynamical systems, chaos and complexity theory and also in the modeling of certainindustrial and financial processes. An operator f acting from a set X to X, satisfyingthe functional equation f(f(x)) = F(x) (for every x from X) is called ”square root”of the given operator F acting from X to X. The problem of computing square rootsof operators (if exists) remains a hard task. While the theory of functional equationsprovides some insight for the iterative roots of real and complex valued functions, iterative roots of mappings in high dimensional spaces are almost not studied and thereare little contributions to numerical algorithms for their computation. We prove existence of iterative roots of a certain class of monotone mappings in Hilbert spaces,generalizing the scalar case result for strictly monotone functions. We demonstratehow methods based on neural networks and statistical learning theory can find squareroots of trajectories of certain dynamical systems.
Using Online Social Networks for Social Geography Studies
Alexey Yashunsky1 and Nadezda Zamiatina2
1Keldysh Institute of Applied Mathematics, Russia
2Geography Department, Moscow State University, Russia
,
Research in social and economic geography more often than not relies on various statistics as raw data. Hence, the lack of trustworthy and detailed statistical materials may become a hinderance. Whereas developed countries (e.g. USA, EU countries) have vast statistic databases open to the public, the emerging economies and developing countries to this day still have very limited statistical information available.
This statistical vacuum forces researchers to look for other sources of information. These can be found, for instance, within online social networking services. Although this information is hardly representative of the entire population and never absolutely trustworthy, it can still be used to study certain social groups.
These research techniques may be of interest even for developed countries for studying phenomena that are not reflected by official statistics.
We have recently carried out some basic research on "knowledge spillover" in modern Russia using public data from the vk.com social network. The studied cases revealed some interesting spacial patterns in the origin and later employment locations of several Russian Universities' students. Further and deeper analysis may allow identification of the so-called bonding and bridging connections for Universities and trace their spacial components so as to evaluate their influence on creative and labor force migrations in modern Russia.
The challenges for network analysis in this area are both technical and theoretical. On the one hand, processing social network data with geographical goals requires the development of specific tools, on the other hand, formal network-level criteria could help the identification of certain geography-specific phenomena.
A New Algorithm of Network Decomposition and its Application for Stock Market Analysis
Boris Goldengorin1, Panos Pardalos1,2, Alexander Rubchinsky1
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
,,
The network decomposition problem is one of the well-known «classical» problems of network analysis. Informal character and great diversity of applications have led to many different formal statements of the problem. The essence of the suggested approach consists in a new combination of two known ideas: finding a cut by the so called frequency method and checking statistical stability of obtained divisions. In both directions new modifications are suggested.
The algorithm is constructed as a multistage procedure. A result of every stage is a family of decompositions that firstly is gradually expanded and after gradually contracted so that the output of the entire procedure consists of one decomposition.