Улучшение качества разбиения графа с помощью многоуровневой оптимизации
Graph partitioning is required for solving tasks on graphs that need to be split across disks or computers. This problem is well studied, but most results are not suitable for processing graphs with billons of nodes on commodity clusters, since they require shared memory or low-latency messaging. One approach suitable for cluster computing is Balanced Label Propagation, based on distributed label propagation algorithm for community detection. In this work we show how multi-level optimization can be used to improve partitioning quality of Balanced Label Propagation. One of major difficulties with distributed multi-level optimization is finding a matching in the graph. The matching is needed to choose pairs of vertices for collapsing in order to produce a smaller graph. As this work shows, simply splitting graph into several parts and finding matching in these parts independently is enough to improve the quality of partitioning generated by Balanced Label Propagation. Proposed algorithm can be implemented within any framework that supports MapReduce. In our experiments, when graphs were partitioned into 32 parts, ratio of edges that don’t cross partitions increased from 54-60% to 66-70%. One of significant problems of our implementation is performance – work time of multi-level algorithm was approximately twice that of the original algorithm. It seems likely that implementation can be improved so that multi-level algorithm would achieve better computational performance as well as partitioning quality.
By analyzing the logs of corporate e-mail networks we found a number of patterns, showing how the size of ego-networks of individual employees changes on a day by day basis. We proposed a simple model that adequately describes the observed time dependence of an employee's "social circle". Comparison of experimental data with the theoretical model showed that employees are divided into two groups - with fast and slow changes in their social circles, respectively. We believe that the presence of these groups reflects both project-type and process-type of employees' activities. Comparison of data obtained before and during the global economic crisis has shown that the crisis led to an actual reduction in project-type activities.
Legal pluralism and the experience of the state in the Caucasus are at the centre of this edited volume. This is a region affected by a multitude of legal orders and the book describes social action and governance in the light of this, and considers how conceptions of order are enforced, used, followed and staged in social networks and legal practice. Principally, how is the state perceived and how does it perform in both the North and South Caucasus? From elections in Dagestan and Armenia to uses of traditional law in Ingushetia and Georgia, from repression of journalism in Azerbaijan to the narrations of anti-corruption campaigns in Georgia - the text reflects the multifarious uses and performances of law and order. The collection includes approaches from different scholarly traditions and their respective theoretical background and therefore forms a unique product of multinational encounters.
This book presents recent research developments in social networks, economics, management, marketing and optimization applied to sports. The volume will be of interest to students, researchers, managers from sports, policy makers and as well athletes. In particular the book contains research papers and reviews addressing the following issues: social network tools for player selection, movement and pricing in team sports, methods for ranking teams and evaluating players' performance, economics and marketing issues related to sports clubs, techniques for predicting outcomes of sports competitions, optimal strategies in sports, scheduling and managing sports tournaments, optimal referee assignment techniques and the economics and marketing of sports entertainment.
This book presents a course of English for Specific Purposes devoted specifically to the widely-discussed topic Web 2.0. It covers several aspects of online communication ranging from online friendship to business interacions. The activities presented in the coursebook are aimed at developing students’ communicative competence in both written and oral discourse. Web 2.0 includes a variety of authentic articles that arouse interest and provoke discussions. It also presents listening texts based on professional podcasts. Most grammar and vocabulary activities are developed from authentic texts as well.
Web 2.0 can be used at the B2-C1 levels of Common European Famework. The coursebook will help learn and practice the target vocabulary. It will be relevant to those interested in the development of Information and Communication Technologies in general and the Internet in particular.
The article discusses the phenomenon of interconnected glocal hospitality communities which have recently spread over the world in the context of the internet development and cultural globalization processes. It focuses on a typical community of users of CouchSurfi ng.org, a major social hospitality network in St. Petersburg. The author argues that, in the framework of this web service, there occurs a transformation of virtual groups of users localized in various spots of the globe into actual interconnected glocal communities which shape shared identities, norms, values, and practices among its members.
The following article is devoted to analysis of civil identity's social foundations through the actor-network theory framework. Three aspects are considered: the specific character of civic identity as a subject-object interaction between the actor and the state, the network interactions in the «real» and «virtual» spaces, social memory, social and cultural experience, socially-relevant knowledge as a basis for forming a shared social context of civic identity.
There have been implemented engineering and development of multi-agent recommender system «EZSurf» that performs analysis of interests and provides recommendations for the social network «VKontakte» users based on the data from profile of particular user. During the work process different methods and technological solutions have been analyzed with examination of their advantages and disadvantages. Besides of that the comparative analysis of analogous products has been held where the most similar is Russian start-up service - Surfingbird. Based on this analysis the decision of recommender system implementation and integration has been accepted. The feature of this system is that it uses social network “VKontakte” profile for user’s data collection and API of third-party services (LastFM, TheMovieDB) for an extraction of information about similar objects. Such an approach contributes into optimization of recommender system, because it does not require creation of its own object classification system and objects database. The functionality of multi-agent system was separated between three agents. First agent (Collector) collects user data from “VKontakte” profile using VK API. Second agent (Analyzer) collects similar objects from databases of thitd-party services (LastFM, TheMovieDB) that will be the criteria for further search of recommendatory content. For search and selection of information an agent (Recommender) that works as web-crawler has been implemented. System «EZSurf» can be exploited by the users of social network “VKontakte” in everyday life for time economy on web-surfing process. At the same time they will get recommendations on content that are filtered depending on preferences of every particular user.
A model for organizing cargo transportation between two node stations connected by a railway line which contains a certain number of intermediate stations is considered. The movement of cargo is in one direction. Such a situation may occur, for example, if one of the node stations is located in a region which produce raw material for manufacturing industry located in another region, and there is another node station. The organization of freight traﬃc is performed by means of a number of technologies. These technologies determine the rules for taking on cargo at the initial node station, the rules of interaction between neighboring stations, as well as the rule of distribution of cargo to the ﬁnal node stations. The process of cargo transportation is followed by the set rule of control. For such a model, one must determine possible modes of cargo transportation and describe their properties. This model is described by a ﬁnite-dimensional system of diﬀerential equations with nonlocal linear restrictions. The class of the solution satisfying nonlocal linear restrictions is extremely narrow. It results in the need for the “correct” extension of solutions of a system of diﬀerential equations to a class of quasi-solutions having the distinctive feature of gaps in a countable number of points. It was possible numerically using the Runge–Kutta method of the fourth order to build these quasi-solutions and determine their rate of growth. Let us note that in the technical plan the main complexity consisted in obtaining quasi-solutions satisfying the nonlocal linear restrictions. Furthermore, we investigated the dependence of quasi-solutions and, in particular, sizes of gaps (jumps) of solutions on a number of parameters of the model characterizing a rule of control, technologies for transportation of cargo and intensity of giving of cargo on a node station.
Event logs collected by modern information and technical systems usually contain enough data for automated process models discovery. A variety of algorithms was developed for process models discovery, conformance checking, log to model alignment, comparison of process models, etc., nevertheless a quick analysis of ad-hoc selected parts of a journal still have not get a full-fledged implementation. This paper describes an ROLAP-based method of multidimensional event logs storage for process mining. The result of the analysis of the journal is visualized as directed graph representing the union of all possible event sequences, ranked by their occurrence probability. Our implementation allows the analyst to discover process models for sublogs defined by ad-hoc selection of criteria and value of occurrence probability
The geographic information system (GIS) is based on the first and only Russian Imperial Census of 1897 and the First All-Union Census of the Soviet Union of 1926. The GIS features vector data (shapefiles) of allprovinces of the two states. For the 1897 census, there is information about linguistic, religious, and social estate groups. The part based on the 1926 census features nationality. Both shapefiles include information on gender, rural and urban population. The GIS allows for producing any necessary maps for individual studies of the period which require the administrative boundaries and demographic information.
Existing approaches suggest that IT strategy should be a reflection of business strategy. However, actually organisations do not often follow business strategy even if it is formally declared. In these conditions, IT strategy can be viewed not as a plan, but as an organisational shared view on the role of information systems. This approach generally reflects only a top-down perspective of IT strategy. So, it can be supplemented by a strategic behaviour pattern (i.e., more or less standard response to a changes that is formed as result of previous experience) to implement bottom-up approach. Two components that can help to establish effective reaction regarding new initiatives in IT are proposed here: model of IT-related decision making, and efficiency measurement metric to estimate maturity of business processes and appropriate IT. Usage of proposed tools is demonstrated in practical cases.