Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2017 | Book

Linear Max-Min Fairness in Multi-commodity Flow Networks Read chapter Read first chapter

Models, Algorithms, and Technologies for Network Analysis

NET 2016, Nizhny Novgorod, Russia, May 2016

Editors: Valery A. Kalyagin, Alexey I. Nikolaev, Panos M. Pardalos, Oleg A. Prokopyev

Publisher: Springer International Publishing

Book Series : Springer Proceedings in Mathematics & Statistics

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This valuable source for graduate students and researchers provides a comprehensive introduction to current theories and applications in optimization methods and network models. Contributions to this book are focused on new efficient algorithms and rigorous mathematical theories, which can be used to optimize and analyze mathematical graph structures with massive size and high density induced by natural or artificial complex networks. Applications to social networks, power transmission grids, telecommunication networks, stock market networks, and human brain networks are presented.

Chapters in this book cover the following topics:

Linear max min fairness

Heuristic approaches for high-quality solutions

Efficient approaches for complex multi-criteria optimization problems

Comparison of heuristic algorithms

New heuristic iterative local search

Power in network structures

Clustering nodes in random graphs

Power transmission grid structure

Network decomposition problems

Homogeneity hypothesis testing

Network analysis of international migration

Social networks with node attributes

Testing hypothesis on degree distribution in the market graphs

Machine learning applications to human brain network studies

This proceeding is a result of The 6th International Conference on Network Analysis held at the Higher School of Economics, Nizhny Novgorod in May 2016. The conference brought together scientists and engineers from industry, government, and academia to discuss the links between network analysis and a variety of fields.

Table of Contents

Frontmatter

Optimization

Frontmatter
Linear Max-Min Fairness in Multi-commodity Flow Networks
Abstract
In this paper, a linear max-min fairness (LMMF) approach using goal programming is proposed. The linear model in this approach is a bi-objective model where the flow is maximized in one objective, and the fairness in flow is maximized for the other objective. This model can be applied to max- min fairness (MMF) problems in networks with applications to multi-commodity flows in networks. The proposed model provides high flexibility for the decision maker to determine the level of throughput and the fairness of flow in the network. The goal of this paper is to find a less-complex approach to find MMF flow in multi-commodity networks. An example is presented to illustrate the methodology.
Hamoud Bin Obaid, Theodore B. Trafalis
Heuristic for Maximizing Grouping Efficiency in the Cell Formation Problem
Abstract
In our paper, we consider the Cell Formation Problem in Group Technology with grouping efficiency as an objective function. We present a heuristic approach for obtaining high-quality solutions of the CFP. The suggested heuristic applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated many times for randomly generated cell configurations. Our computational experiments are performed for popular benchmark instances taken from the literature with sizes from 10\(\,\times \,\)20 to 50\(\,\times \,\)150. Better solutions unknown before are found for 23 instances of the 24 considered. The preliminary results for this paper are available in Bychkov et al. (Models, algorithms, and technologies for network analysis, Springer, NY, vol. 59, pp. 43–69, 2013, [7]).
Ilya Bychkov, Mikhail Batsyn, Panos M. Pardalos
Efficient Methods of Multicriterial Optimization Based on the Intensive Use of Search Information
Abstract
In this paper, an efficient approach for solving complex multicriterial optimization problems is proposed. For the problems being solved, the optimality criteria may be multiextremal ones, and calculating the criteria values may require a large amount of computations. The proposed approach is based on reducing multicriterial problems to nonlinear programming problems via the minimax convolution of the partial criteria, reducing dimensionality by using Peano evolvents, and applying efficient information-statistical global optimization methods. The new contribution is that all the search information obtained in the course of optimization is used to find each current Pareto-optimal solution. The results of the computational experiments show that the proposed approach essentially reduces the computational costs of solving multicriterial optimization problems (by tens and hundreds of times).
Victor Gergel, Evgeny Kozinov
Comparison of Two Heuristic Algorithms for a Location and Design Problem
Abstract
The article is devoted to the decision-making methods for the following location and design problem. The Company is planning to locate its facilities and gain profit at an already existing market. Therefore it has to take into consideration such circumstances as already placed competing facilities; the presence of several projects for each facility opening; the share of the served demand is flexible and depends on the facility location. The aim of the Company is to determine its new facilities locations and options in order to attract the biggest share of the demand. Modeling flexible demand requires exploiting nonlinear functions which complicates the development of the solution methods. A Variable Neighborhoods Search algorithm and a Greedy Weight Heuristic are proposed. The experimental analysis of the algorithms for the instances of special structure has been carried out. New best known solutions have been found, thus denoting the perspective of the further research in this direction.
Alexander Gnusarev
A Class of Smooth Modification of Space-Filling Curves for Global Optimization Problems
Abstract
This work presents a class of smooth modifications of space-filling curves applied to global optimization problems. These modifications make the approximations of the Peano curves (evolvents) differentiable in all points, and save the differentiability of the optimized function. To evaluate the proposed approach, some results of numerical experiments with the original and modified evolvents for solving global optimization problems are discussed.
Alexey Goryachih
Iterative Local Search Heuristic for Truck and Trailer Routing Problem
Abstract
Vehicle Routing Problem is a well-known problem in logistics and transportation. There is a big variety of VRP problems in the literature, as they arise in many real-life situations. It is a NP-hard combinatorial optimization problem and finding an exact optimal solution is practically impossible in real-life formulations. There is an important subclass of VRP, which is called Truck and Trailer Routing Problem. For this class of problems, every vehicle contains truck and, possibly, trailer parts. In this work, Site-Dependent Truck and Trailer Routing Problem with Hard and Soft Time Windows and Split Deliveries are considered. We develop an Iterative Local Search heuristic for solving this problem. The heuristic is based on the local search approach and also allows infeasible solutions. A greedy heuristic is applied to construct an initial solution.
Ivan S. Grechikhin

Network Models

Frontmatter
Power in Network Structures
Abstract
We consider an application of power indices, which take into account preferences of agents for coalition formation proposed for an analysis of power distribution in elected bodies to reveal most powerful (central) nodes in networks. These indices take into account the parameters of the nodes in networks, a possibility of group influence from the subset of nodes to single nodes, and intensity of short and long interactions among the nodes.
Fuad Aleskerov, Natalia Meshcheryakova, Sergey Shvydun
Do Logarithmic Proximity Measures Outperform Plain Ones in Graph Clustering?
Abstract
We consider a number of graph kernels and proximity measures including commute-time kernel, regularized Laplacian kernel, heat kernel, exponential diffusion kernel (also called “communicability”), etc., and the corresponding distances as applied to clustering nodes in random graphs and several well-known datasets. The model of generating random graphs involves edge probabilities for the pairs of nodes that belong to the same class or different predefined classes of nodes. It turns out that in most cases, logarithmic measures (i.e., measures resulting after taking logarithm of the proximities) perform better while distinguishing underlying classes than the “plain” measures. A comparison in terms of reject curves of interclass and intra-class distances confirms this conclusion. A similar conclusion can be made for several well-known datasets. A possible origin of this effect is that most kernels have a multiplicative nature, while the nature of distances used in cluster algorithms is an additive one (cf. the triangle inequality). The logarithmic transformation is a tool to transform the first nature to the second one. Moreover, some distances corresponding to the logarithmic measures possess a meaningful cutpoint additivity property. In our experiments, the leader is usually the logarithmic Communicability measure. However, we indicate some more complicated cases in which other measures, typically, Communicability and plain Walk, can be the winners.
Vladimir Ivashkin, Pavel Chebotarev
Analysis of Russian Power Transmission Grid Structure: Small World Phenomena Detection
Abstract
In this paper, the complex network theory is used to analyze the spatial and topological structure of the Unified National Electricity Grid (UNEG)—Russia’s power transmission grid, the major part of which is managed by Federal Grid Company of the Unified energy system. The research is focused on the applicability of the small-world model to the UNEG network. Small-world networks are vulnerable to cascade failure effects what underline importance of the model in power grids analysis. Although much research has been done on the applicability of the small-world model to national power transmission grids, there is no generally accepted opinion on the subject. In this paper we, for the first time, used the latticization algorithm and small-world criterion based on it for transmission grid analysis. Geo-latticization algorithm has been developed for a more accurate analysis of infrastructure networks with geographically referenced nodes. As the result of applying the new method, a reliable conclusion has been made that the small-world model is applicable to the UNEG. Key nodes and links which determine the small-world structure of the UNEG network have been revealed. The key power transmission lines are critical for the reliability of the UNEG network and must be the focal point in preventing large cascade failures.
Sergey Makrushin
A New Approach to Network Decomposition Problems
Abstract
A new approach to network decomposition problems (and, hence, to classification problems, presented in network form) is suggested. Opposite to the conventional approach, consisting in construction of one, “the most correct” decomposition (classification), the suggested approach is focused on the construction of a family of classifications. Based on this family, two numerical indices are introduced and calculated. The suggested indices describe the complexity of the initial classification problem as whole. The expedience and applicability of the elaborated approach are illustrated by two well-known and important cases: political voting body and stock market. In both cases, the presented results cannot be obtained by other known methods. It confirms the perspectives of the suggested approach.
Alexander Rubchinsky
Homogeneity Hypothesis Testing for Degree Distribution in the Market Graph
Abstract
The problem of homogeneity hypothesis testing for degree distribution in the market graph is studied. Multiple hypotheses testing procedure is proposed and applied for China and India stock markets. The procedure is constructed using bootstrap method for individual hypotheses and Bonferroni correction for multiple testing. It is shown that homogeneity hypothesis of degree distribution for the stock markets for the period of 2003–2014 is not accepted.
D. P. Semenov, P. A. Koldanov
Stability Testing of Stock Returns Connections
Abstract
The problem of stability of connections of stock returns over time is considered. This problem is formulated as a multiple testing problem of homogeneity of covariance matrices. A statistical procedure based on Box’s M-test and Bonferroni correction is proposed. This procedure is applied to French and German stock markets.
M. A. Voronina, P. A. Koldanov

Applications

Frontmatter
Network Analysis of International Migration
Abstract
Our study employs the network approach to the problem of international migration. During the last years, migration has attracted a lot of attention and has been examined from many points of view. However, very few studies considered it from the network perspective. The international migration can be represented as a network (or weighted directed graph) where the nodes correspond to countries and the edges correspond to migration flows. The main focus of our study is to reveal a set of critical or central elements in the network. To do it, we calculated different existing and new centrality measures. In our research the United Nations International Migration Flows Database (version 2015) was used. As a result, we obtained information on critical elements for the migration process in 2013.
Fuad Aleskerov, Natalia Meshcheryakova, Anna Rezyapova, Sergey Shvydun
Overlapping Community Detection in Social Networks with Node Attributes by Neighborhood Influence
Abstract
Community detection is one of the key instruments in social network analysis. In social networks nodes (people) have many attributes such as gender, age, hometown, interests, workplace, etc., which can form possibly overlapping communities. But quite often full information about a person’s attributes cannot be obtained due to data loss, privacy issues, or person’s own accord. A fast method for overlapping community detection in social networks with node attributes is presented. The proposed algorithm is based on attribute transfer from neighbor vertices, and does not require any knowledge of attributes meaning. It was evaluated on Facebook and Twitter datasets with ground-truth communities and four classic graphs: Zachary’s karate club, books about US politics, American college football, and US political blogs. Also, author’s ego-network with manually labeled communities from VKontakte was used for the evaluation. Experiments show that the proposed method outperforms such algorithms as Infomap, modularity maximization, CESNA, BigCLAM, and AGM-fit by \(F_1\)-score and Jaccard similarity coefficient by more than 10%. The algorithm is tolerant to node attributes partial absence: more than 50% of attributes values can be deleted without great loss in accuracy. It has a near-linear runtime in the network size and can be easily parallelized.
Vladislav Chesnokov
Testing Hypothesis on Degree Distribution in the Market Graph
Abstract
In this chapter, problems of testing hypotheses on degree distribution in the market graph and of identifying power law in data are discussed. Research methodology of power law hypothesis testing is presented. This methodology is applied to testing hypotheses on degree distribution in the market graphs for different stock markets. Obtained results are discussed.
P. A. Koldanov, J. D. Larushina
Application of Network Analysis for FMCG Distribution Channels
Abstract
The paper presents the approach for multidimensional analysis of marketing tactics of the companies employing network tools. The research suggests omni-channel distribution tactic of a company as a node in eight-dimensional space. Dimensions for node location are defined by frequency of usage of eight communication channels (friends, acquaintances, telephone, home presentations, printed advertisement, internet, e-mail, and door to door). The comparison is grounded on measuring pairwise distance between nodes in eight-dimensional space. Pairwise distance measured by Euclidean norm is used as a weight of edge between companies. The smaller the Euclidean distance, the higher is similarity. Further, we employ network representation of multidimensional statistics to analyze performance and companies’ characteristic, such as product category, market share, education level, and average age of distributors. Empirical implication is approved on the sample from 5694 distributors from 16 fast moving consumer goods (FMCG) distributing companies from direct selling industry.
Nadezda Kolesnik, Valentina Kuskova, Olga Tretyak
Machine Learning Application to Human Brain Network Studies: A Kernel Approach
Abstract
We consider a task of predicting normal and pathological phenotypes from macroscale human brain networks. These networks (connectomes) represent aggregated neural pathways between brain regions. We point to properties of connectomes that make them different from graphs arising in other application areas of network science. We discuss how machine learning can be organized on brain networks and focus on kernel classification methods. We describe different kernels on brain networks, including those that use information about similarity in spectral distributions of brain graphs and distances between optimal partitions of connectomes. We compare performance of the reviewed kernels in tasks of classifying autism spectrum disorder versus typical development and carriers versus noncarriers of an allele associated with an increased risk of Alzheimer’s disease.
Anvar Kurmukov, Yulia Dodonova, Leonid E. Zhukov
Co-author Recommender System
Abstract
Modern bibliographic databases contain significant amount of information on publication activities of research communities. Researchers regularly encounter challenging task of selecting a co-author for joint research publication or searching for authors, whose papers are worth reading. We propose a new recommender system for finding possible collaborator with respect to research interests. The recommendation problem is formulated as a link prediction within the co-authorship network. The network is derived from the bibliographic database and enriched by the information on research papers obtained from Scopus and other publication ranking systems.
Ilya Makarov, Oleg Bulanov, Leonid E. Zhukov
Network Studies in Russia: From Articles to the Structure of a Research Community
Abstract
Our research focuses on the structure of a research community of Russian scientists involved in network studies, which is studied by means of analysis of articles published in Russian-language journals. The direction of network studies in Russia is quite new form of research methodology—however, in recent years we can observe the growing number of scientists working at this direction and institutionalized forms of their cooperation. Studying the structure of these researchers’ community is important for the fields development. This paper is the first report on the research, that is why it focuses on methodological issues. It covers the description of method of citation (reference) analysis that we use and the process of data collection from eLibrary.ru resource, as well as presents some brief overview of collected data (based on analysis of 8 000 papers). It is concluded by representation of future steps of the research.
Daria Maltseva, Ilia Karpov
Metadata
Title
Models, Algorithms, and Technologies for Network Analysis
Editors
Valery A. Kalyagin
Alexey I. Nikolaev
Panos M. Pardalos
Oleg A. Prokopyev
Copyright Year
2017
Electronic ISBN
978-3-319-56829-4
Print ISBN
978-3-319-56828-7
DOI
https://doi.org/10.1007/978-3-319-56829-4

Premium Partner

    Image Credits