Baez, category data, permutation

 https://math.ucr.edu/home/baez/

https://twitter.com/johncarlosbaez

permutations: https://math.ucr.edu/home/baez/permutations/

graph permutation, isomorphism, 3xor hypothesis

3xor hypothesis

Yuan Zhou, hardness of robust graph isomorphism, Lassere gaps, and asymmetry of random graphs
https://www.youtube.com/watch?v=gAsQsEMgWU0

Given two graphs which are almost isomorphic, is it possible to find a bijection which preserves most of the edges between the two? This is the algorithmic task of Robust Graph Isomorphism, which is a natural approximation variation of the Graph Isomorphism problem. In this talk, we show that no polynomial-time algorithm solves this problem, conditioned on Feige's Random 3XOR Hypothesis. In addition, we show that the Lasserre/SOS SDP hierarchy, the most powerful SDP hierarchy known, fails quite spectacularly on this problem: it needs a linear number of rounds to distinguish two isomorphic graphs from two far-from-isomorphic graphs. Along the way, we venture into the theory of random graphs by showing that a random graph is robustly asymmetric whp, meaning that any permutation which is close to an automorphism is itself close to the identity permutation. Joint work with Ryan O'Donnell, John Wright, and Chenggang Wu.

permutation graphs

https://en.wikipedia.org/wiki/Permutation_graph

View on ScienceDirect

Algorithmic Graph Theory and Perfect Graphs, Volume 57

2nd Edition

Write a review

Authors: Martin Golumbic

eBook ISBN: 9780080526966

Hardcover ISBN: 9780444515308

Imprint: North Holland

Published Date: 4th February 2004

Page Count: 340

View all volumes in this series: Annals of Discrete Mathematics

mathramp, 2014 Oct 28

Rstudio was not moved into "Application".

Went over R code for simulating aging in permuted networks.

Went over R code for generating histogram of CV

ms02_singlerun_v2() test

The code has trouble to deal with small network with many selfing or redundant pairs. 

Test on 48 states runs OK.

Gompertz and Weibull fitting, yGINDIP vs ms02, repliminary

lapbio-hq:mathramp hqin$ pwd

/Users/hqin/github/mactower-network-failure-simulation/mathramp

ms02 network aging, preliminary

I run preliminary analysis on network aging, and found that ms02 network tend to have short maximum network lifespan, even though their average lifespan is more or less the same with the yeast GIN/PPI. This seem to suggests that ms02 network has a more homogenous aging process. It seems to make sense that power-law increase heterogeneity in the yeast network. 

Population size of 500 did not good p-value using wilcox.test().

self-pairing test, ms02, R, network permutation

test network: 

Expectation: When ncycles run to 1, the last row should be "NA"

Summary: the code 'ms02' passed the test. No extra row or self-pairs are found.

2014April 7. 'ms02' did not check id1-id2 versus id2-id1. 

R, permute network without selfpairing, bug fix

#permute merged yeast PPI+GIN, fix a bug that insert "NA" into new networks. 

#require(igraph)
rm(list=ls())
debug = 0
set.seed(2014)
permute.pairs.wo.selfpairs = function( inpairs,  ncycles=10, debug=1 ) {#bug, id1-id2 and id2-id1 are not considered. 
  if (ncycles >= 1 ) {
    if(debug) {
      print(paste('ncycles=', ncycles))
    }
    longids = c(as.character(inpairs[,1]), as.character(inpairs[,2]) )
    longids = sample(longids)
    len = length(inpairs[,1])
    newpairs = data.frame( cbind( longids[1:len], longids[(len+1): (2*len)]) )
    names(newpairs) = c('id1', 'id2')
    newpairs$id1 = as.character( newpairs$id1)
    newpairs$id2 = as.character( newpairs$id2)    
    newpairs$selfpairs = ifelse( newpairs$id1 == newpairs$id2, 1, 0 )
    self.tb = newpairs[ newpairs$selfpairs==1, ]
    nonself.tb = newpairs[newpairs$selfpairs==0, ]
    if(debug) {
      print(paste("===selfpairs===="),NULL)
      print(self.tb)
      print(paste("================="),NULL)
    }
    if( length(self.tb[,1])>=1 ) {
      if ( ncycles == 0) { 
        #return (c(NA,NA, NA) );
        print(paste("ncycles reached zero, ncycles"),ncycles)
        print(paste("Abort!"),NULL)
        stop; 
      } else {
        ncycles = ncycles - 1
        splitPos = round( length(self.tb[,1]) * sqrt(ncycles) ) + 5  #2014 Jan 31 changes
        selectedpairs = rbind(self.tb,  nonself.tb[1: splitPos, ] )
        restpairs = nonself.tb[ (splitPos + 1): length(nonself.tb[,1]), ]
        return( rbind(restpairs, permute.pairs.wo.selfpairs(selectedpairs, ncycles)))
      }
    } else {  
      return (newpairs)
    }
  } else {
    return( c(NA,NA,NA )) 
  }
}

#write.table(pairs, "merged_PPIGIN_2014Jan20.tab", quote=F, row.names=F, col.names=F, sep='\t')
net = read.table( "merged_PPIGIN_2014Jan20.tab", header=F, sep="\t", colClass = c("character", "character") )
head(net)
if(debug==9) { 
  #net = read.table('pair.tab',header=F) 
 net = net[1:90000,]
}


net2 = permute.pairs.wo.selfpairs( net  )
write.csv(net2, "/tmp/net2.csv")
write.csv(net,"/tmp/net.csv")

#do they have the same degree?
t1 = table(c(net[,1],net[,2]))
t2 = table(c(net2[,1],net2[,2]))
comp <- t1 == t2
table(comp)
tf = comp[comp==F]; tf
t1[names(tf)[1]]
t1[names(tf)]
t2[names(tf)]



#note, this R code runs even faster than ms02, presumably because ms02 spent time on network configuration. 

#2014 April 7. Bug found. id1-id2, id2-id1 should be considered. 

ms02 run, ubuntu server

run.sh
ms02 -i merged_PPIGIN_2014Jan20.tab -o output/_ms02.merged.network.tab -d 2

nohup sh run.sh &

2014-1-31, 12:42 1.8% MEM
System clearly responded slower as soon as the job started.

2014-1-31, 12:46, 'top' shows that 'free' Mem is declining rapidly, suggesting memory leaking of 'ms02'.

Out of application disk space caused by 'ms02'

helen:ms02GINPPI hqin$ cat run.sh
ms02 -i merged_PPIGIN_2014Jan20.tab -o output/_m202.merged.network.tab -d 2

'ms02' may have memory leak and ran out memory.

I remotely login to 'helen.spelman.edu', and found that the shell still works.

I should try R script for comparison.