Two Novel Evolutionary Formulations of the Graph Coloring Problem

We introduce two novel evolutionary formulations of the problem of coloring the nodes of a graph. The first formulation is based on the relationship that exists between a graph's chromatic number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The second formulation, unlike the first one, does not tackle one graph at a time, but rather aims at evolving a program to color all graphs belonging to a class whose members all have the same number of nodes and other common attributes. The heuristics that result from these formulations have been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and have been found to be competitive when compared to the several other heuristics that have also been tested on those graphs.     

Algorithm for the Cost Edge-Coloring of Trees

Let C be a set of colors, and let be a cost function which assigns a real number (c) to each color C in C. An edge-coloring of a graph G is to color all the edges of G so that any two adjacent edges are colored with different colors. In this paper we give an efficient algorithm to find an optimal edge-coloring of a given tree T, that is, an edge-coloring f of T such that the sum of costs (f(e)) of colors f(e) assigned to all edges e is minimum among all edge-colorings of T. The algorithm takes time O(n²) if n is the number of vertices and is the maximum degree of T.     

Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Given a finite set V and a set function , we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in time, where is the time to compute the value of f(X) for a subset .     

Exponential random graph model specifications for bipartite networks—A dependence hierarchy

In this paper, we review the development of dependence structures for exponential random graph models for bipartite networks, and propose a hierarchy of dependence structures within which different dependence assumptions may be located. Based on this hierarchy, we propose a new set of model specifications by including bipartite graph configurations involving more than four nodes. We discuss the theoretical significance of the various effects that the extended models afford, and illustrate application of this hierarchy of models to several bipartite networks related to the political mobilization in Brazil in the early 1990s (Mische, 2007).     

近年来我国问卷调查方法的新发展

问卷调查是一种介入性研究方式,问卷调查资料是研究者、问卷、访问员、受访者、访谈情境共同建构的结果,而非关于研究对象的“客观事实”。近年来,学者们从“交流准则”、“语境”、“心理二重区域”、“过程控制”的角度对问卷调查进行的反思,深化了对调查误差的认识。抽样的规范化和绘图抽样的使用,是近年来调查抽样的新趋势。     

An online algorithm for continuous slab caster scheduling

Lee et al. (Lee, K., Chang, S.Y., and Hong, Y., 2004. Continuous slab caster scheduling and interval graphs. Production Planning & Control, 13 (5), 495–501) have introduced a slab caster scheduling problem and developed an optimal algorithm. Their algorithm is efficient but an offline algorithm that we need the information on all the customer orders a priori to implement. In this article, we propose an online algorithm that we can implement without knowledge of the orders yet to arrive. We show that the offline version of our new algorithm also provides an optimal solution and the online version has the worst case performance ratio of 3. We also give a short proof on the correctness of Lee et al.'s algorithm.     

基于模糊图的模糊社会网络定义及其性质分析

以模糊图的概念及其基本性质为基础,定义了模糊社会网络的基本概念,并探讨了其相关的一些基本性质。这些概念的定义及其相关分析,为进一步进行模糊社会网络分析提供了基本的理论依据。     

双模拟及其一些基本性质

模拟和互模拟是分别比同态和同构弱的一对概念,论文给出一个比模拟强但又比互模拟弱的概念——双模拟,并考察与此相关的一些问题:在模拟的基础上,定义"双模拟"的概念,并说明如何从双模拟得到互模拟;证明双模拟的一些基本性质;讨论模拟、互模拟与双模拟之间的关系。     

Revisiting asymmetric marriage rules

Although generalized exchange remains an emblematical model of alliance theory, characterizing matrimonial systems as pertaining to this model is tricky. The necessary condition of generalized exchange is the deliberate preference for asymmetric exchanges. Given a marriage dataset, can we determine whether the observed pattern is due to the realization of a social norm enjoining symmetric or asymmetric exchange or is the result of random processes? Here, relevant probabilities and indexes are established in the framework of graph theory, and are validated using a demographic individual-based model. The methods are applied to three datasets from the literature, allowing to assess with great confidence that the observed marriage configurations were not random.     

Friends in locked places: An investigation of prison inmate network structure

The current study investigates informal social structure among prison inmates. Data come from the Prison Inmate Network Study (PINS), a project focused on a unit of a Pennsylvania medium security men’s prison. We focus on 205 inmates and their “get along with” network – an approximation of friendship in other settings. We find a weak subgroup structure dominated by two groups of “old heads” and characterized by moderate (non gang-based) race/ethnic clustering. Structurally, the network resembles adolescents in schools, suggesting that prison inmates are capable of successfully building peer associations. We conclude that under the right conditions self-organizing inmate society can foster social integration reminiscent of other social settings.