Models, Algorithms and Technologies for Network Analysis, Springer Proceedings in Mathematics & Statistics
The contributions in this volume cover a broad range of topics including maximum cliques, graph coloring, data mining, brain networks, Steiner forest, logistic and supply chain networks. Network algorithms and their applications to market graphs, manufacturing problems, internet networks and social networks are highlighted. The "Fourth International Conference in Network Analysis," held at the Higher School of Economics, Nizhny Novgorod in May 2014, initiated joint research between scientists, engineers and researchers from academia, industry and government; the major results of conference participants have been reviewed and collected in this Work. Researchers and students in mathematics, economics, statistics, computer science and engineering will find this collection a valuable resource filled with the latest research in network analysis.
We characterize the graphs whose induced subgraphs all have the following property: The maximum number of induced 4-paths is equal to the minimum cardinality of the set of vertices such that every induced 4-path contains at least one of them. In this chapter we describe all such graphs obtained from simple cycles by replacing some vertices with cographs.
We consider a game equilibrium in a network in each node of which an economy is described by the simple two-period model of endogenous growth with production and knowledge externalities. Each node of the network obtains an externality produced by the sum of knowledge in neighbor nodes. Uniqueness of the inner equilibrium is proved. Three ways of behavior of each agent are distinguished: active, passive, and hyperactive. Behavior of agents in dependence on received externalities is studied. It is shown that the equilibrium depends on the network structure. We study the role of passive agents and, in particular, possibilities of connection of components of active agents through components of passive agents. Changes of the equilibrium under changes in the network structure are studied. It is shown that appearance of a new link, as a rule, leads to decrease of knowledge in all nodes, but sometimes knowledge in some nodes increases. A notion of type of node is introduced and classification of networks based on this notion is provided. It is shown that the inner equilibrium depends not on the size of network but on its structure in terms of the types of nodes, and in similar networks of different size agents of the same type behave in similar way.
Random matrix theory (RMT) is applied to investigate the cross-correlation matrix of a financial time series in four different stock markets: Russian, American, German, and Chinese. The deviations of distribution of eigenvalues of market correlation matrix from RMT global regime are investigated. Specific properties of each market are observed and discussed.
The cell formation problem (CFP) is an NP-hard optimization problem considered for cell manufacturing systems. Because of its high computational complexity several heuristics have been developed for solving this problem. In this paper we present a branch and bound algorithm which provides exact solutions of the CFP. This algorithm finds optimal solutions for 13 problems of the 35 popular benchmark instances from the literature.