An Exact Algorithm for Blockmodeling of Two-Mode Network Data

We consider problems where relationships between two sets (or modes) of objects are available in the form of a binary matrix with elements of 1 (0) indicating a bond (lack of a bond) between corresponding row and column objects. The goal is to establish a partition of the row objects and, simultaneously, a partition of the column objects to form blocks that consist of either exclusively 1s or exclusively 0s to the greatest extent possible. This two-mode blockmodeling problem arises in several scientific domains. In the social sciences, two-mode blockmodeling is particularly relevant for social network analysis, where the goal is to simultaneously partition a set of individuals and another set of objects (e.g., events they attended, organizations they are affiliated with, etc.). The inherent computational challenge of simultaneously constructing partitions for two distinct sets of objects has fostered a reliance on heuristics for two-mode blockmodeling. We offer an exact algorithm and demonstrate its efficacy in a simulation study. Two applications to real-world networks are also provided.     

完全多部图的符号边控制数的界

$f: E(G)\rightarrow\{-1,1\}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=\sum_{e''\in N[e]}f(e'')\geq1$对于图$G$的每条边$e\in E$都成立. $w(f)=\sum_{e\in E}f(e)$称为函数$f$的权. $G$的符号边控制数$\gamma_{s}\,''(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.     

Structural balance in fully signed networks

Node attributes play an important role in shaping network structures, but are generally ignored in transformations of structural balance. A fully signed network consisting of signs of edges and nodes expresses both properties of relationship and node attributes. In this article, we generalize the definition of structural balance in fully signed networks. We transform the unbalanced fully signed network by not only changing signs of edges but also changing the signs of nodes. We propose a memetic algorithm to transform unbalanced networks at the lowest cost. Experiments show that our algorithm can solve this problem efficiently, and different node attribute assignments may lead to different optimized structures. © 2016 Wiley Periodicals, Inc. Complexity 21: 497–511, 2016     

Three‐dimensional blockmodels

In the classic blockmodel formulation, a social network among members of a population with n actors and k relations (types of tie) is arrayed as k n X n matrices. Though this is a three‐dimensional data structure, it is typically reduced to a two‐way analysis. In this paper, a three‐way procedure for analyzing multigraph data is developed. Specifically, in addition to applying the rule of structural equivalence to collapse actors, it is also applied to the relations (the third dimension), and structurally equivalent sets of relations are collapsed. The result is a three‐dimensional blockmodel (image) of social structure that is a more parsimonious representation of social structure than the classic two‐dimensional blockmodel images. The three‐dimensional approach is illustrated by application to three case studies: Homan's Bank Wiring Room, Sampson's monastery, and a local economy of hospital services. The structural equivalence approach to relations is further explored by applying it to the individual‐level Liking and Antagonism relations and their compounds (of length four or less) in the Bank Wiring Room. This application demonstrates that the structural equivalence approach can be used to identify equality equations for primitive and compound relations.     

Hilbert空间H中带符号广义框架的一个刻画

本文研究了可分的Hilbert空间H中带符号广义框架,利用算子理论方法,给出了H中一族向量{hm}m∈M是一个带符号广义框架当且仅当带符号广义框架的框架算子的正部S 和负部S-是有界线性算子,讨论了H中带符号广义框架的框架算子S的可逆性,并且得到了H中每个向量f关于带符号广义框架{hm}m∈M和其对偶带符号广义框架{~hm}m∈M的表示式.     

Balance Theory with Incomplete Awareness

In this paper, we reformulate balance theory by allowing actors to possess incomplete awareness of the evaluations held by other actors, and by adopting balance closure (modified to allow incomplete awareness) as an equilibrium concept. Our treatment highlights psychological mechanisms, maintains a clear distinction between actors and objects, emphasizes the effects of self-awareness and self-evaluations of actors, and permits actors to hold ambivalent (simultaneously positive and negative) evaluations. Our analysis extends previous results linking the imbalance of a signed graph to ambivalence in its balance closure and reveals that an actor's “indirect awareness” of imbalance is necessary but not sufficient for that actor's ambivalence in the balance closure.     

REPRESENTATION OF GENERALIZED TRANSLATIONS OF THE PRODUCT OF TWO FUNCTIONS ON SIGNED HYPERGROUPS ON THE REAL LINE

In this paper,we consider the generalized translations associated with the Dunkl and the Jacobi-Dunkl differential-difference operators on the real line which provide the structure of signed hrpergroups on R.Especially,we study the representation of the generalized translations of the product of two functions for these signed hypergroups.     

Nowhere‐Zero Flows on Signed Complete and Complete Bipartite Graphs

Bouchet's conjecture asserts that each signed graph which admits a nowhere‐zero flow has a nowhere‐zero 6‐flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow‐admissible graph admits a nowhere‐zero 4‐flow and we characterise those which have a nowhere‐zero 2‐flow and a nowhere‐zero 3‐flow.     

Six-flows on almost balanced signed graphs

In 1983, Bouchet conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow. By Seymour's 6-flow theorem, Bouchet's conjecture holds for signed graphs with all edges positive. Recently, Rollová et al proved that every flow-admissible signed cubic graph with two negative edges admits a nowhere-zero 7-flow, and admits a nowhere-zero 6-flow if its underlying graph either contains a bridge, or is 3-edge-colorable, or is critical. In this paper, we improve and extend these results, and confirm Bouchet's conjecture for signed graphs with frustration number at most two, where the frustration number of a signed graph is the smallest number of vertices whose deletion leaves a balanced signed graph.     

平衡子欧拉符号图及符号线图

符号图$S=(S^u,\sigma)$是以$S^u$作为底图并且满足$\sigma: E(S^u)\rightarrow\{+,-\}$. 设$E^-(S)$表示$S$的负边集. 如果$S^u$是欧拉的(或者分别是子欧拉的, 欧拉的且$|E^-(S)|$是偶数, 则$S$是欧拉符号图(或者分别是子欧拉符号图, 平衡欧拉符号图). 如果存在平衡欧拉符号图$S''$使得$S''$由$S$生成, 则$S$是平衡子欧拉符号图. 符号图$S$的线图$L(S)$也是一个符号图, 使得$L(S)$的点是$S$中的边, 其中$e_ie_j$是$L(S)$中的边当且仅当$e_i$和$e_j$在$S$中相邻,并且$e_ie_j$是$L(S)$中的负边当且仅当$e_i$和$e_j$在$S$中都是负边. 本文给出了两个符号图族$S$和$S''$,它们应用于刻画平衡子欧拉符号图和平衡子欧拉符号线图. 特别地, 本文证明了符号图$S$是平衡子欧拉的当且仅当$\not\in S$, $S$的符号线图是平衡子欧拉的当且仅当$S\not\in S''$.     

Structural cohesion and embeddedness in two-mode networks

The detection of structural cohesion is a key utility of social network analysis, but little work has been done to refine the detection of structural cohesion in two-mode networks. Most work on cohesion in two-mode networks either: (1) attempts to detect cohesion in such networks using one-mode projections (which can be problematic for reasons we discuss); or (2) focuses on restrictive substructures like bi-cliques to identify cohesive subgroups. We propose a new strategy for two-mode networks that follows the general reasoning of approaches to detecting structural cohesion in one-mode networks. Our approach identifies the number of actors from one node set that may be removed before disconnecting actors in the opposite set. We also develop a definition of embeddedness that draws on Moody and White’s hierarchical nesting approach.     

How Many Communities Are There?

Stochastic blockmodels and variants thereof are among the most widely used approaches to community detection for social networks and relational data. A stochastic blockmodel partitions the nodes of a network into disjoint sets, called communities. The approach is inherently related to clustering with mixture models; and raises a similar model selection problem for the number of communities. The Bayesian information criterion (BIC) is a popular solution, however, for stochastic blockmodels, the conditional independence assumption given the communities of the endpoints among different edges is usually violated in practice. In this regard, we propose composite likelihood BIC (CL-BIC) to select the number of communities, and we show it is robust against possible misspecifications in the underlying stochastic blockmodel assumptions. We derive the requisite methodology and illustrate the approach using both simulated and real data. Supplementary materials containing the relevant computer code are available online.     

Network modelling and variational Bayesian inference for structure analysis of signed networks

Currently, structure analysis of signed networks with positive and negative links has received wide attention and is becoming a research focus in the area of network science. In recent years, many community detection methods for signed networks have been proposed to analyze the structure of signed networks. However, current methods can only efficiently analyze the signed networks with the single community structure and unable to analyze the signed networks with the coexisting structure of communities and peripheral nodes, bipartite, or other structures. To address this problem, in this study, we present a mathematically principled method for the structure analysis of signed networks with positive and negative links, in which a probabilistic model firstly is proposed to model the signed networks with the single community or the coexisting structure, and a variational Bayesian approach is deduced to learn the approximate distribution of model parameters. For determining the optimal model, we also deduce a model selection criterion based on the evidence theory. In addition, to efficiently analyze the large signed networks, we propose a fast learning version of our algorithm with the time complexity O(k²E) where k is the number of groups and E is the number of links. In our experiments, the proposed method is validated in the synthetic and real-world signed networks, and is compared with the state-of-the-art methods. The experimental results demonstrate that the proposed method can more efficiently and accurately analyze to the structure of signed networks than the state-of-the-art methods.     

Signed degree sets in signed graphs

The set D of distinct signed degrees of the vertices in a signed graph G is called its signed degree set. In this paper, we prove that every non-empty set of positive (negative) integers is the signed degree set of some connected signed graph and determine the smallest possible order for such a signed graph. We also prove that every non-empty set of integers is the signed degree set of some connected signed graph.     

Oriented hypergraphs: Balanceability

An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques that generalize the circuit classification of the signed graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camion's algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance.     

Signed graphs for portfolio analysis in risk management

We introduce the notion of structural balance for signed graphsin the context of portfolio analysis. A portfolio of securitiescan be represented as a signed graph with the nodes denotingthe securities and the edges representing the correlation betweenthe securities. With signed graphs, the characteristics of aportfolio from a risk management perspective can be uncoveredfor analysis purposes. It is shown that a portfolio characterizedby a signed graph of positive and negative edges that is structurallybalanced is characteristically more predictable. Investors whoundertake a portfolio position with all positively correlatedsecurities do so with the intention to speculate on the upside(or downside). If the portfolio consists of negative edges andis balanced, then it is likely that the position has a hedgingdisposition within it. On the other hand, an unbalanced signedgraph is representative of an investment portfolio which ischaracteristically unpredictable.     

Strongly invertible links and divides

To a proper generic immersion of a finite number of copies of the unit interval in a 2-disc, called a divide, A’Campo associates a link in S³. From the more general notion of ordered Morse signed divides, one obtains a braid presentation of links of divides. In this paper, we prove that every strongly invertible link is isotopic to the link of an ordered Morse signed divide. We give fundamental moves for ordered Morse signed divides and show that strongly invertible links are equivalent if and only if we can pass from one ordered Morse signed divide to the other by a sequence of such moves. Then we associate a polynomial to an ordered Morse signed divide, invariant for these moves. So this polynomial is invariant for the equivalence of strongly invertible links.     

Signed graph factors and degree sequences

For a signed graph G and function , a signed f‐factor of G is a spanning subgraph F such that sdeg_F(υ) = f(υ) for every vertex υ of G, where sdeg(υ) is the number of positive edges incident with v less the number of negative edges incident with υ, with loops counting twice in either case. For a given vertex‐function f, we provide necessary and sufficient conditions for a signed graph G to have a signed f‐factor. As a consequence of this result, an Erd?s‐Gallai‐type result is given for a sequence of integers to be the degree sequence of a signed r‐graph, the graph with at most r positive and r negative edges between a given pair of distinct vertices. We discuss how the theory can be altered when mixed edges (i.e., edges with one positive and one negative end) are allowed, and how it applies to bidirected graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 27–36, 2006     

Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication

We consider a stochastic blockmodel equipped with node covariate information, that is, helpful in analyzing social network data. The key objective is to obtain maximum likelihood estimates of the model parameters. For this task, we devise a fast, scalable Monte Carlo EM type algorithm based on case-control approximation of the log-likelihood coupled with a subsampling approach. A key feature of the proposed algorithm is its parallelizability, by processing portions of the data on several cores, while leveraging communication of key statistics across the cores during each iteration of the algorithm. The performance of the algorithm is evaluated on synthetic datasets and compared with competing methods for blockmodel parameter estimation. We also illustrate the model on data from a Facebook derived social network enhanced with node covariate information. Supplemental materials for this article are available online.     

关于图符号的边控制 (英)

设γ's(G)和γ'ι(G)分别表示图G的符号边和局部符号边控制数,本文主要证明了:对任何n阶图G(n≥4),均有γ's(G)≤[11/6n-1]和γ'ι(G)≤2n-4成立,并提出了若干问题和猜想．