Listen to your pc music through your phone

So I have this bunch of music on my external hard drive that is connected to my PC at home and I need to get over there to play it while I’m at home, but that’s usually a hassle, well, to some extent. So, here is a partial solution to it. I ssh into my PC from my phone and play the music, and listen to it from my bluetooth loud speakers or headphone, while doing my other things at home (specially in the morning having breakfast).

Starting an ssh server on linux:

service sshd start

This should open the port 22. Check it by:

netstat -ant | grep 22
tcp     0     0     192.168.122.1:53     0.0.0.0:*           LISTEN 
tcp     0     0     0.0.0.0:22           0.0.0.0:*           LISTEN 
tcp     0     0     192.168.0.15:44664   192.0.78.22:443     ESTABLISHED
tcp     0   468     192.168.0.15:22      192.168.0.11:33814  ESTABLISHED
tcp     0     0     192.168.0.15:44648   192.0.78.22:443     ESTABLISHED
tcp6    0     0     :::22                :::*                LISTEN

If I want the server to start on boot I can do this:

chkconfig sshd on

Then I need to figure out what is my PC’s local IP address so that I can ssh into it. A quick way to do it is by looking at the output at ifconfig and going through to find the corresponding IP. Right now mine looks like this:

enp0s25: flags=4099<UP,BROADCAST,MULTICAST>  mtu 1500
        ether **:85:**:0b:**:6c  txqueuelen 1000  (Ethernet)
        RX packets 0  bytes 0 (0.0 B)
        RX errors 0  dropped 0  overruns 0  frame 0
        TX packets 0  bytes 0 (0.0 B)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions 0
        device interrupt 19  memory 0xf0500000-f0520000  

lo: flags=73<UP,LOOPBACK,RUNNING>  mtu 65536
        inet 127.0.0.1  netmask 255.0.0.0
        inet6 ::1  prefixlen 128  scopeid 0x10
        loop  txqueuelen 1  (Local Loopback)
        RX packets 468  bytes 36452 (35.5 KiB)
        RX errors 0  dropped 0  overruns 0  frame 0
        TX packets 468  bytes 36452 (35.5 KiB)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions 0

virbr0: flags=4099<UP,BROADCAST,MULTICAST>  mtu 1500
        inet 192.168.122.1  netmask 255.255.255.0  broadcast 192.168.122.255
        ether 00:00:00:00:00:00  txqueuelen 1000  (Ethernet)
        RX packets 0  bytes 0 (0.0 B)
        RX errors 0  dropped 0  overruns 0  frame 0
        TX packets 0  bytes 0 (0.0 B)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions 0

wlp48s0: flags=4163<UP,BROADCAST,RUNNING,MULTICAST>  mtu 1500
        inet 192.168.0.15  netmask 255.255.255.0  broadcast 192.168.0.255
        inet6 ****:6477:****:73e2:****:d8ff:****:e8b2  prefixlen 64  scopeid 0x0
        inet6 fe80::****:d8ff:****:e8b2  prefixlen 64  scopeid 0x20
        ether **:16:**:36:**:b2  txqueuelen 1000  (Ethernet)
        RX packets 970380  bytes 1163277882 (1.0 GiB)
        RX errors 0  dropped 0  overruns 0  frame 0
        TX packets 469268  bytes 56819419 (54.1 MiB)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions

and that second line under wlp48s0 will be my ip. Since I’m using a dynamic ip assignment, this might change every time my PC connects to network, so I have written a script that runs at startup and looks this up (and my public ip) every one hour and writes it to a file in my dropbox so that I can access it from my phone! Here it is:

#!/bin/bash
while true; do
    ifconfig wlp48s0 | grep cast > ~/Dropbox/opt/myip
    wget http://ipecho.net/plain -O - -q >> ~/Dropbox/opt/myip
    sleep 1h
done

ssh clients for android and some shortcuts

The next step is to run a ssh client on my phone. Currently I’m using JuiceSSH, but I think I’ll be moving to ConnectBot or some other free apps soon, or probably I should just run a terminal on my phone and ssh from there. After connecting to 192.168.0.15 on port 22 I can browse through the files on my PC and run them. Since my external hard drive has a long name and is mounted somewhere that requires me to remember a lot of things I just added an alias to the .bashrc file so that I can directly go to my music folder:

alias cdmusic="cd 'path/to/my music/folder/'"

Then I find the folder I wanna play and use mplayer to play it. Since I had this other script to personalize my mplayer a little bit, I keep using that to play all the files in a folder in a fashinable way:

alias play="mplayer -msgcolor -cache 500 20 *.*"

You can find the full list in the mplayer man page: man mplayer (See the bottom of the post). And if that’s too much, here is short list of  essential ones from mplayer --help:

Selection_017

You could also turn your phone into a remote control for your video playback this way! I should still find good ways to do this over internet, and stream the music to my phone rather than to a bluetooth device! I mean, I don’t want an entire personal cloude running on my PC, but why not!

 

bluetooth and audio settings

In order to have a bluetooth device automatically connect to your PC you can do this:

bluetoothctl

This will show a list of all the bluetooth devices, their MAC addresses, and their names. Then I can “trust” them by typing

trust de:vi:ce:ma:ca:dd:re:ss

This makes my device to connect to the PC automatically when it’s on (read the help for complete set of commands and options). Now to change the sound output to each device I can do this, assuming pulse audio is in use:

pacmd list-cards

I get a list of audio devices and lots of descriptions. Somewhere there you should be able to find your bluetooth device and an “index” related to it. mine is “3” right now (but it changes each time the device disconnects and connects) for my sound box, and “0” for the PC speakers. Then all I need to do is:

echo "set-default-sink 3" | pacmd

or

echo "set-default-sink 0" | pacmd

to go back to PC.

Partial Update:

Apparently there are ways to assign a static IP to your computer, for example see here, but there are some problems that needs to be worked out afterwards, e.g. disconnecting from internet etc. Fortunately, my modem can set a static IP address for each MAC address that I could manage through its settings. That is, I don’t need to read the IP of my PC each time.

ToDo

  • figure out how to find the correct local ip automatically
  • add the above to my script!
  • figure out how to find the correct index for the sound output device automatically.

Note:
to run a script so that you can change the current directory run it like this:

. myscript

References:


footnotes:

Here is a full list of keyboard shortcuts for mplayer that one can use (even via ssh):

keyboard control
              LEFT and RIGHT
                   Seek backward/forward 10 seconds.
              UP and DOWN
                   Seek forward/backward 1 minute.
              PGUP and PGDWN
                   Seek forward/backward 10 minutes.
              [ and ]
                   Decrease/increase current playback speed by 10%.
              { and }
                   Halve/double current playback speed.
              BACKSPACE
                   Reset playback speed to normal.
              < and >
                   Go backward/forward in the playlist.
              ENTER
                   Go forward in the playlist, even over the end.
              HOME and END
                   next/previous playtree entry in the parent list
              INS and DEL (ASX playlist only)
                   next/previous alternative source.
              p / SPACE
                   Pause (pressing again unpauses).
              .
                   Step forward.  Pressing once will pause movie, every consecutive press will play one frame and then go into pause mode again (any other key unpauses).
              q / ESC
                   Stop playing and quit.
              U
                   Stop playing (and quit if -idle is not used).
              + and -
                   Adjust audio delay by +/- 0.1 seconds.
              / and *
                   Decrease/increase volume.
              9 and 0
                   Decrease/increase volume.
              ( and )
                   Adjust audio balance in favor of left/right channel.
              m
                   Mute sound.
              _ (MPEG-TS, AVI and libavformat only)
                   Cycle through the available video tracks.
              # (DVD, Blu-ray, MPEG, Matroska, AVI and libavformat only)
                   Cycle through the available audio tracks.
              TAB (MPEG-TS and libavformat only)
                   Cycle through the available programs.
              f
                   Toggle fullscreen (also see -fs).
              T
                   Toggle stay-on-top (also see -ontop).
              w and e
                   Decrease/increase pan-and-scan range.
              o
                   Toggle OSD states: none / seek / seek + timer / seek + timer + total time.
              d
                   Toggle frame dropping states: none / skip display / skip decoding (see -framedrop and -hardframedrop).
              v
                   Toggle subtitle visibility.
              j and J
                   Cycle through the available subtitles.
              y and g
                   Step forward/backward in the subtitle list.
              F
                   Toggle displaying "forced subtitles".
              a
                   Toggle subtitle alignment: top / middle / bottom.
              x and z
                   Adjust subtitle delay by +/- 0.1 seconds.
              c (-capture only)
                   Start/stop capturing the primary stream.
              r and t
                   Move subtitles up/down.
              i (-edlout mode only)
                   Set start or end of an EDL skip and write it out to the given file.
              s (-vf screenshot only)
                   Take a screenshot.
              S (-vf screenshot only)
                   Start/stop taking screenshots.
              I
                   Show filename on the OSD.
              P
                   Show progression bar, elapsed time and total duration on the OSD.
              ! and @
                   Seek to the beginning of the previous/next chapter.
              D (-vo xvmc, -vo vdpau, -vf yadif, -vf kerndeint only)
                   Activate/deactivate deinterlacer.
              A    Cycle through the available DVD angles.

              (The following keys are valid only when using a hardware accelerated video output (xv, (x)vidix, (x)mga, etc), the software equalizer (-vf eq or -vf eq2)  or
              hue filter (-vf hue).)

              1 and 2
                   Adjust contrast.
              3 and 4
                   Adjust brightness.
              5 and 6
                   Adjust hue.
              7 and 8
                   Adjust saturation.

              (The following keys are valid only when using the quartz or corevideo video output driver.)

              command + 0
                   Resize movie window to half its original size.
              command + 1
                   Resize movie window to its original size.
              command + 2
                   Resize movie window to double its original size.
              command + f
                   Toggle fullscreen (also see -fs).
              command + [ and command + ]
                   Set movie window alpha.

              (The following keys are valid only when using the sdl video output driver.)

              c
                   Cycle through available fullscreen modes.
              n
                   Restore original mode.

              (The following keys are valid if you have a keyboard with multimedia keys.)

              PAUSE
                   Pause.
              STOP
                   Stop playing and quit.
              PREVIOUS and NEXT
                   Seek backward/forward 1 minute.

              (The following keys are only valid if you compiled with TV or DVB input support and will take precedence over the keys defined above.)

              h and k
                   Select previous/next channel.
              n
                   Change norm.
              u
                   Change channel list.

              (The following keys are only valid if you compiled with dvdnav support: They are used to navigate the menus.)

              keypad 8
                   Select button up.
              keypad 2
                   Select button down.
              keypad 4
                   Select button left.
              keypad 6
                   Select button right.
              keypad 5
                   Return to main menu.
              keypad 7
                   Return to nearest menu (the order of preference is: chapter->title->root).
              keypad ENTER
                   Confirm choice.

              (The following keys are used for controlling TV teletext. The data may come from either an analog TV source or an MPEG transport stream.)

              X
                   Switch teletext on/off.
              Q and W
                   Go to next/prev teletext page.

       mouse control
              button 3 and button 4
                   Seek backward/forward 1 minute.
              button 5 and button 6
                   Decrease/increase volume.

       joystick control
              left and right
                   Seek backward/forward 10 seconds.
              up and down
                   Seek forward/backward 1 minute.
              button 1
                   Pause.
              button 2
                   Toggle OSD states: none / seek / seek + timer / seek + timer + total time.
              button 3 and button 4
                   Decrease/increase volume.
Advertisements

Non-teaching aspects of teaching at University of Calgary

I’ve been a math postdoc at University of Calgary for two years now, and I’ll be here for at least one more year. The teaching environment is very pleasant, and the resources are abundant. Nonetheless, there are a few non-teaching aspects of it that bothers me. The way that the teaching is handled in the mathematics department for postdocs is that we are hired as a sessional instructors, with a no strings attached for the teaching. A course is assigned to us, with a fixed number for the pay. There are no benefits coming with it, and no pension associated to it. However, after 1 year of being a sessional instructor we can apply for $200 reimbursement in professional development activities.

During the first semester that I was here, I didn’t have a teaching duty, but I was offered to teach a course for extra pay, which I took it. However, by the end of semester I realized that I haven’t been paid for my teaching at all. It turned out that it was an error of the accounting personnel of the department which hadn’t put me on payroll (teaching salary is separate from my postdoc salary). Eventually, I got a lump sum for my Fall semester teaching in the following February. A year later when filing for taxes, I realized that getting paid all of it in February wasn’t a good idea, since it resulted in my paying about an extra $1000 in taxes for that year. The case isn’t resolved yet. Well, to be honest, I still don’t know how to even go after fixing this!

Let me tell you a little about how our department counts teaching. Each “regular” course (whatever that means) in a semester counts as one “half course equivalent”, which means a sessional instructor gets paid about $6250 for teaching it, and it counts as “one” teaching duty for a full time faculty member. It turns out that the department counts teaching, for example, a Calculus 1 course (Math 249 or Math 265) with up to 180 students as 1 “half course equivalent” for the faculty, and up to 240 students as 1.5, and up to 360 students as 2 “half course equivalents”. That is, if you are a full time faculty here with teaching load of 2 for the Fall semester, all you need to do is to teach a Calculus 1 course with 360 students in it. The weird part of it is that you don’t get to know any of these things by default, and I couldn’t find any documents in the department talking about this, maybe for lack of trial!

What I have experienced here as a postdoc (sessional instructor) though, is that all of the courses that I’ve taught with 240 students still counts as 1 “half course equivalent”, that is I get paid about $6250 for it, and also I am supposed to run one of the labs for whatever course I teach. I haven’t had any concerns regarding this so far, until there came up a situation about my teaching duties next year. It all started with a simple confusion, in my postdoc contract I was supposed to be teaching one course as part of my responsibilities. So, as I said above, the way that this is handled is that they reduce my negotiated pay by around $6250 and then hire me as a sessional instructor and then pay that amount to me via a separate series of pay checks. The confusion was that the associate head of teaching of the department thought I am supposed to teach two courses as part of my duties, he then scheduled me for one large section (360 students) of Calculus 1 (Math 265), which my new postdoc supervisor objected, as it will consume too much time from me, hence I won’t be able to spend enough time on my research. After a few emails back and forth between people (I wasn’t involved here) I was told that I will be teaching the large section and get paid for two half course equivalents, and even as an “exception” they’ll drop the lab for me! It sounded like an awesome deal. So I agreed.

Until last week that they sent me the contract to be signed, which said I’m getting paid for one half course equivalent. Upon inquir”es” it turned out that the department has decided that “it is pretty fair” if I teach a large section instead of a small section + lab. I’ll probably take the offer, but it leaved me with this question that why there are such double standards segregating the faculty and sessionals, and why the policies in the department are not transparent.

So you wanna move to Canada?

I’ve recently moved to Canada and applied for permanent residency through the Express Entry system. If your situation is similar to me (you have a higher education degree, a few years of part time — yes TA and RA count — or full time experience, you can speak English fair enough) then you might be eligible to enter Canada the same way. To do so, you don’t need to be present in Canada, and you don’t have to remain in Canada the entire time if you don’t think that’s something you’ll want to keep.

There are several ways for moving to Canada, but I know of only one, and I only know a few things about it which is obviously about my case! The way that I applied for immigration to Canada was through the Express Entry process, a somewhat new method which started some time in 2014 I guess. The idea is based on your education, language skills, work experience, age, marital status etc you get a score and enter a pool. Roughly every two weeks the government draws the top people from the pool and invites them to apply for the Express Entry program. That basically means if you have claimed everything correctly, and if you provide all the required documents, and if you have a clean background, then almost surely you’ll get to become a Canadian permanent resident (a five year non-bounding status to live in Canada).

What are your chances to be eligible for Express Entry?

First get a rough estimate of your rating here: http://www.cic.gc.ca/english/immigrate/skilled/crs-tool.asp

Then head over here http://www.cic.gc.ca/english/express-entry/rounds.asp to see the minimum ratings drawn from the pool in the last draw and how others are doing in the pool!

For example, as of my writing, if your score is above 451, andif  in the next round they draw 800 people, you’ll be selected.

What do you need to enter the pool?

Here are the first things you need to do:

  • Take a general IELTS exam at your earliest time. When you are signing up, it asks you what do you need it for, choose for immigration purposes.
  • Evaluate your degrees (all degrees which are not from a Canadian institute). There are a few companies that the Canadian government work with, out of which I only remember WES. Create an account there and fill the forms to tell them what degrees you want to evaluate. Then it will tell you how much you need to pay. After paying it, it will give you a code that you need to keep, and then it will tell you what documents shall you send to them and in what condition. Make sure that the code is mentioned on all the documents.

These are all you need to get into the pool. Do these first and enter the pool as soon as possible. Basically, you claim all the rest and when you get drawn you provide documents to support your claims. So, then start working on the rest of the documents:

  • Work experience. Gather letters from your bosses (preferably your direct supervisors for all the previous jobs, but HR also works) to show your work history. For some countries like Iran you might need to provide your insurance history too. Here is what you need to be in the letter:
    • written on company letterhead,
    • signed by the responsible supervisor,
    • have the printed name and title of the responsible supervisor beneath the signature,
    • show the company’s full address, telephone and fax numbers, e-mail and website addresses,
    • stamped with the company’s official seal (if applicable).
    • the specific period of your employment with the company,
    • the positions you have held during the period of employment and the time spent in each position, and the status of the current positoin
    • main responsibilities and duties in each position,
    • total annual salary plus benefits,
    • the number of hours worked per week

      Your TA and RA also count.  For TA your department head probably is the supervisor. For RA your advisor. Ask them to be very specific about dates, and number of hours, etc. As specific as they can be! Nonetheless all this information is in your contracts.

  • Police records: If you live in US you need one from FBI. At the minimum you want police reports for the countries that you lived in in the past 10 years for at least 6 months. If you need additional reports, they will let you know when you are drawn from the pool.
  • Proof of financial assets: you need about 13000 CND per person in the application. Though per application it might be a different situation. But if that’s the case you need to provide an official letter indicating your financial profile, including
    • list of all your bank (chequing and savings) accounts
    • the account numbers
    • dates each account was opened, and
    • the balance of each account over the past six months,
    • list all outstanding debts, i.e. loans, credit cards, etc,
    • be printed on the letterhead of the financial institution, and include your name and the contact information of the financial institution (address, telephone number and e-mail address).
    • proof of assets, like cars, houses, etc.

     

That’s all for now. I’ll keep adding details here.

Good luck.

 

Miroslav and the separating wand

In a huge graph, it is hard to determine a bottleneck by just looking at it, or doing any type of search. And by a bottleneck, I mean part of graph that is not very much connected to the other part. In different setting this could mean different things, for example, if your graph is a communication network, then a bottleneck mean the information doesn’t get to all of the nodes very easily, there will be traffic around the bottleneck.

images.duckduckgo.comOne of the celebrated results in algebraic graph theory is by Miroslav Fiedler, a Czech mathematician [1, 2], about the algebraic connectivity of a graph. It simply says the second smallest eigenvalue of the Laplacian matrix of a graph determines how connected the graph is. In particular, if it is 0, the graph is disconnected. Furthermore, it shows the eigenvector corresponding to this eigenvalue distinguishes the vertices in the two connected components. In the case that the graph is connected, this eigenvector will find bottlenecks of the graph. Below I first generate a random graph that has a visible bottleneck, then I’ll use Fiedler’s result to find it computationally.

First, let’s generate a random graph with a bottleneck. In order to do so, I’ll generate two random graphs, then I look at their disjoint union and put few random edges between them.

def random_bottleneck_graph(n1,n2,p1,p2,p):
    #n1 = number of vertices of first part
    #n2 = number of vertices of second part
    #p1 = probability of edges of first part
    #p2 = probability of edges of second part
    #p  = probability of edges between two parts
    
    import random
    
    #generate two parts randomly and put them together
    H1 = graphs.RandomGNP(n1,p1) #generate a random GNP graph for first part
    H2 = graphs.RandomGNP(n2,p2) #generate a random GNP graph for second part
    G = H1.disjoint_union(H2) #form the disjoint union of the two parts
    
    #add edges between two parts
    for i in range(n1): #pick each vertex in H1
        for j in range(n2): #pick each vertex in H2
            a = random.random() #generate a random number between 0 and 1
            if a > 1-p: #with probability p add an edge between the two vertices of H1 and H2
                G.add_edge([(0,i),(1,j)])
    return(G)

And here is a sample run:

#initialization
n1 = 40 #number of vertices of first part
n2 = 60 #number of vertices of second part
p1 = .7 #probability of edges of first part
p2 = .6 #probability of edges of second part
p = .01 #probability of edges between two parts

#run
G = random_bottleneck_graph(n1,n2,p1,p2,p)

Of course when I look at the graph, sage who has generated it knows that the graph has two main parts, and even the vertices are numbered in a way that anyone can recognize it. The left picture is generated by the above ‘show’ command, and the right picture is using the following code.

sage0sage1

def show_random_bottleneck_graph(G,layout=None):
    EdgeColors={'red':[], 'blue':[], 'black':[]}

    for e in G.edges():
        if not e[0][0] == e[1][0]:
            EdgeColors['black'].append(e)
        elif e[0][0] == 0:
            EdgeColors['red'].append(e)
        else:
            EdgeColors['blue'].append(e)
            
    G.show(vertex_labels=False,figsize=[10,10],layout=layout,edge_colors=EdgeColors)

So, in order to really get a random graph with a bottleneck, I take the above graph and try to loose the information that I had from it.

def relable_graph(G,part=None):
    # input: a graph G
    # output: if part is not given, it gives a random labeling of nodes of graph with integers
    #         if part is given, then it partitions the vertices of G labeling each vertex with pairs (i,j) where i in the number of partition the vertex is in part, and j is an integer.
    
    V = G.vertices()
    E = G.edges()
    
    H = Graph({})
    
    map = {}
    if part == None:
        new_part = None
        import random
        random.shuffle(V)
        
        for i in range(len(V)):
            map[V[i]] = i
    else:
        new_part = [ [] for p in part]
        count = 0
        for i in range(len(part)):
            for w in part[i]:
                map[w] = (i,w)
                new_part[i].append((i,w))
                count += 1
    
    for v,w,l in E:
        H.add_edge([map[v],map[w],l])

    return(H,new_part)

###############################
#run
H = relable_graph(G)[0]
H.show(layout='circular',vertex_labels=False, figsize=[10,10])

Now if I look at the graph I won’t be able to recognize the bottleneck:

sage3

Now that I truly have random graph, which I know has a visible bottleneck, let’s see if we can find it. Below I use ‘networkx’ to compute the Fiedler vector, an eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix. Then I’ll partition the vertices according to the sign of the corresponding entry on this vector:

def partition_with_fiedler(G):
    # input: a graph G
    # algorithm: using networkx finds the fiedler vector of G
    # a partitioning of vertices into two pieces according to positive and negative entries of the Fiedler vector
    
    import networkx
    H = G.networkx_graph()
    f = networkx.fiedler_vector(H, method='lanczos')
    
    V = H.nodes()
    P = [[],[]]
    for i in range(len(V)):
        if f[i] >= 0:        
            P[0].append(V[i])
        else:
            P[1].append(V[i])
    
    return(P)

Let’s see how it is partitioned:

P = partition_with_fiedler(H)
H.show(partition=P, layout='circular', vertex_labels=True, figsize=[10,10])

sage4

Well, not much can be seen yet. Now let me put the red vertices in one side and the blue vertices in the other side:

def position_bottleneck(G):
    P = partition_with_fiedler(G)
    
    V = G.vertices()
    new_pos = {}
    
    for v in V:
        if v in P[0]:
            new_pos[v] = [6*(1+random.random()),6*(2*random.random()-1)]
        else:
            new_pos[v] = [-6*(1+random.random()),6*(2*random.random()-1)]

    return(new_pos)
pos = position_bottleneck(H)
H.show(partition=P, pos=pos, vertex_labels=True, figsize=[10,10])

sage5

Now it’s easy to see the bottleneck of the graph! We can even recover the original picture as follows:

(K,newP) = relable_graph(H,part=P)
K.show(partition=newP, layout='circular', vertex_labels=False, figsize=[10,10])

sage6

And here is the representation of it using the colored edges:

show_random_bottleneck_graph(K,layout='circular') #suggested layouts are "circular" and "spring"

sage7.png


UPDATE:

Since I posted this, I’ve been thinking about multiway Fiedler clustering. Here is what I got so far. First I define a list N of number of vertices in each part, and a matrix A which is basically a probability matrix where entry (i,j) is the probability of an edge between part i and part j, hence it is symmetric. If you choose diagonal entries close to 1 and off-diagonal entries close to zero, then you’ll get a graph with multiple communities. I’ll shuffle the vertices around after creating the multi-community graph.

def multi_bottleneck_graph(N,A):
    #N = list of size n of number of vertices in each part
    #A = an nxn matrix where entry (i,j) shows the probability of edges between part i and part j of vertices, and n is the number of parts.
    
    import random
    
    n = len(N)
    G = Graph({})
    
    
    #add vertices for each part
    for i in range(n):
        for j in range(N[i]):
            G.add_vertex((i,j))
    
    V = G.vertices()
    
    #add edges
    for v in V:
        for w in V:
            if not v == w:
                a = random.random() #generate a random number between 0 and 1
                p = A[v[0],w[0]]
                if a > 1-p: #with probability p add an edge between the two vertices of H1 and H2
                    G.add_edge([v,w])
            
    return(G)

def relable_graph(G,part=None):
    # input: a graph G
    # output: if part is not given, it gives a random labeling of nodes of graph with integers
    #         if part is given, then it partitions the vertices of G labeling each vertex with pairs (i,j) where i in the number of partition the vertex is in part, and j is an integer.
    
    V = G.vertices()
    E = G.edges()
    
    H = Graph({})
    
    map = {}
    if part == None:
        new_part = None
        import random
        random.shuffle(V)
        
        for i in range(len(V)):
            map[V[i]] = i
    else:
        new_part = [ [] for p in part]
        count = 0
        for i in range(len(part)):
            for w in part[i]:
                map[w] = (i,w)
                new_part[i].append((i,w))
                count += 1
    
    for v,w,l in E:
        H.add_edge([map[v],map[w],l])

    return(H,new_part)

def shuffled_multi_bottleneck_graph(N,A):
    G = multi_bottleneck_graph(N,A)
    H = relable_graph(G)[0]
    return(H)

# run
N = [10,15,20]
A = matrix([[.9,.01,.01],[.01,.9,.01],[.01,.01,.9]])
G = shuffled_multi_bottleneck_graph(N,A)
G.show(layout='circular',vertex_labels=False, vertex_size=30, figsize=[10,10])

sage10

Then I break the graph into two pieces using Fiedler vector, compare the two pieces according their algebraic connectivities (second smallest eigenvalue of the Laplacian) and break the smaller one into two pieces and repeat this process, until I get n communities.

def partition_with_fiedler(G):
    # input: a graph G
    # algorithm: using networkx finds the fiedler vector of G
    # a partitioning of vertices into two pieces according to positive and negative entries of the Fiedler vector
    
    import networkx
    H = G.networkx_graph()
    f = networkx.fiedler_vector(H, method='lanczos')
    
    V = H.nodes()
    P = [[],[]]
    for i in range(len(V)):
        if f[i] >= 0:        
            P[0].append(V[i])
        else:
            P[1].append(V[i])
    
    return(P)
    

def multi_fiedler(G,n=2):
    if n == 2:
        P = partition_with_fiedler(G)
        return(P)
    
    else:
        import networkx

        P = partition_with_fiedler(G)
        H = [ G.subgraph(vertices=P[i]) for i in range(2) ]
        C = [ (networkx.algebraic_connectivity(H[i].networkx_graph(), method='lanczos')/H[i].order(),i) for i in range(2) ]
        l = min(C)[1]
        
        while n > 2:
            n = n-1
            
            temP = partition_with_fiedler(H[l])
            nul = P.pop(l)
            P.append(temP[0])
            P.append(temP[1])

            
            temH = [ G.subgraph(vertices=temP[i]) for i in range(2) ]
            nul = H.pop(l)
            H.append(temH[0])
            H.append(temH[1])
        
             
            temC = [ (networkx.algebraic_connectivity(temH[i].networkx_graph(), method='lanczos')/temH[i].order(),i) for i in range(2) ]
            nul = C.pop(l)
            C.append(temC[0])
            C.append(temC[1])
            l = min(C)[1]
            
        return(P)
# run
G.show(partition=K, layout='circular', figsize=[10,10])

sage12

Now I can separate same colour vertices to see the communities in the graph:

def show_communities(G,n):
    #G: a graph
    #n: number of communities > 1
    if n == 1:
        P = [G.vertices()]
    elif n > 1:
        P = multi_fiedler(G,n)
    else:
        raise ValueError('n > 0 is the number of communities.')
    L,newP = relable_graph(G,part=P)
    L.show(partition=newP, layout='circular', vertex_labels=False, figsize=[10,10])

# run
show_communities(G,3)

sage11

There is only one important thing in using networkx. It seems like the default method (tracemin) for algebraic_connectivity and for fiedler_vector has a bug. So, I used the method=’lanczos’ option there.

You might be interested to see what happens if you ask for more or less than 3 communities. Here are a couple of them:

sage22sage24

The next question is how to decide about number of communities.


  1. M. Fiedler, Algebraic connectivity of graphs. Czechoslovak Math. J. 23(98):298–305 (1973).
  2. M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J. 25:619–637, (1975).

Two New Movies

I recently went to a couple of screening which made me really happy.

C6aJXKZWgAIgoxQFirst film was “gifted“, the story of a first grader who has a special talent in mathematics and people struggle making a decision between letting her to be an ordinary kid, or coaching her hard to become one of the greatest mathematicians of history. Though the story is somewhat beefed up to become a holywood movie, it shows some of the aspects of the life very nicely. The movie overall was made well, and very much recommended. Gifted will be coming to US theatres on April 7 and Canada theatres on April 12.

Trailer: GIFTED

 

Screenshot at 2017-04-05 12-32-49.pngThe second movie was “codegirl“, more of a documentary about groups of high school girls attacking real life problems in their communities by developing mobile apps. The first scene is a quote from Justin Wolfers, an economist and public policy scholar:

FEWER LARGE COMPANIES
ARE RUN
BY WOMEN THAN BY MEN NAMED JOHN

The movie opens in a small town in Moldova, showing the problems with clean drinking water. The movie goes on to show some of the teams’ early progresses, their struggles, and the emotional moments when a team advances to the next level or gets eliminated. The contrast of types of problems each team has to deal with depending on where they’re from is shown very clearly and beautifully in the movie. The final scenes announcing what some of the teams (eliminated or otherwise) are doing with their projects is particularly inspiring. Highly recommended.

Trailer: CODEGIRL

Nonsymmetric SIEP paper is published in LAA

My first solo paper “Existence of a Not Necessarily Symmetric Matrix with Given Distinct Eigenvalues and Graph” got published in Journal of Linear Algebra and its Applications, yesterday. It took it exactly one year! I’ve written about it here: Losing the Symmetry.

The main idea is to use the implicit function theorem to perturb the following matrix in a way that entries corresponding to the edges become nonzero, and by adjusting the rest of the entries to get back to the original spectrum.

Selection_321Selection_322

You can find the published version here (download for the first 50 days is free).