- Oct 17 2017 physics.soc-ph cs.SI arXiv:1710.05265v1The dismantling network problem only asks the minimal vertex set of a graph after removing which the remaining graph will break into connected components of sub-extensive size, but we should also consider the efficiency of intermediate states during the entire dismantling process, which is measured by the general performance R in this paper. In order to improve the general performance of the belief-propagation decimation (BPD) algorithm, we introduce a compound algorithm (CA) mixing the BPD and the node explosive percolation (NEP) algorithm. In this CA, the NEP algorithm will rearrange and optimize the head part of a dismantling sequence given by the BPD. Two ancestor algorithms are connected at the joint point where the general performance can be optimized. It dismantles a graph to small pieces as quickly as the BPD, and it is with the efficiency of the NEP during the entire dismantling process. We find that a wise joint point is where the BPD breaks the original graph to subgraphs no longer larger than the 1% of the original one. We refer the CA with this settled joint point as the fast CA and the fast CA is in the same complexity class with the BPD algorithm. The computation on some real-world instances also exhibits that using the fast CA to optimize the intermediate process of a dismantling algorithm is an effective approach.
- Oct 17 2017 physics.soc-ph arXiv:1710.05744v1A signed network represents how a set of nodes are connected by two logically contradictory types of links: positive and negative links. Examples are signed product networks where two products can be complementary (purchased together) or substitutable (purchased instead of each other). Such contradictory types of links may play dramatically different roles in the spreading process of information, opinion etc. In this work, we propose a Self-Avoiding Pruning (SAP) random walk on a signed network to model e.g. a user's purchase activity on a signed network of products and information/opinion diffusion on a signed social network. Specifically, a SAP walk starts at a random node. At each step, the walker moves to a positive neighbour that is randomly selected and its previously visited node together with its negative neighbours are removed. We explored both analytically and numerically how signed network features such as link density and degree distribution influence the key performance of a SAP walk: the evolution of the pruned network resulting from the node removals of a SAP walk, the length of a SAP walk and the visiting probability of each node. Our findings in signed network models are further partially verified in two real-world signed networks.
- Oct 17 2017 physics.soc-ph q-bio.PE arXiv:1710.05807v1
- Oct 17 2017 physics.soc-ph arXiv:1710.05589v1
- Oct 17 2017 physics.soc-ph cs.SI arXiv:1710.05272v1
- Oct 17 2017 physics.soc-ph arXiv:1710.05754v1
- Oct 17 2017 physics.soc-ph arXiv:1710.05752v1