milkbox.net

2009_01_05
Community Structure Mark Newman has written a bunch of papers on determining community structure in networks, particularly social networks. The idea is that a group of people are considered a community if the ratio of intercommunity connections are greater than the external connections to that community. The quality of a particular choice of community is measured against that of choosing edges randomly and by using some simple mathematical formulas we can calculate this very easily. However, choosing the "best" community structure for a network is not as easy. Originally the algorithms worked by creating weights for each edge in the network, then connecting nodes based on these weights which would in turn create new connected components which would be the communities. What Newman and Girvan introduced was to give edges weights based on a betweeness value which is the number of shortest paths that go through each edge. Of course, the problem is that even with a fast betweeness calculation (which also happens to be contributed by Newman), the runtime even on a sparse graph of n vertices is somewhere in the O(n**3) range. Well, there is also an algorithm provided first by Girvan and Newman, and then improved by Newman, that is essentially a greedy optimization problem that can calculate the improvement of joining two vertices into a community. Essentially the algorithm initially takes all vertices as individual communities and then based on their degrees and the degrees of their neighbors, calculates which two vertices will improve the quality of our community choice (remember that in a very large network there are countably infinite number of ways to organize the graph into communities). The result is a tree (dendrogram) of community divisions. Basically a heirarchy of communities. The only thing that is somewhat discerning (although good to know) is that the contact graphs, at least the sparse ones, are not turning out to be very community oriented.

2009_01_05

Community Structure Mark Newman has written a bunch of papers on determining community structure in networks, particularly social networks. The idea is that a group of people are considered a community if the ratio of intercommunity connections are greater than the external connections to that community. The quality of a particular choice of community is measured against that of choosing edges randomly and by using some simple mathematical formulas we can calculate this very easily.

However, choosing the "best" community structure for a network is not as easy. Originally the algorithms worked by creating weights for each edge in the network, then connecting nodes based on these weights which would in turn create new connected components which would be the communities.

What Newman and Girvan introduced was to give edges weights based on a betweeness value which is the number of shortest paths that go through each edge. Of course, the problem is that even with a fast betweeness calculation (which also happens to be contributed by Newman), the runtime even on a sparse graph of n vertices is somewhere in the O(n**3) range.

Well, there is also an algorithm provided first by Girvan and Newman, and then improved by Newman, that is essentially a greedy optimization problem that can calculate the improvement of joining two vertices into a community. Essentially the algorithm initially takes all vertices as individual communities and then based on their degrees and the degrees of their neighbors, calculates which two vertices will improve the quality of our community choice (remember that in a very large network there are countably infinite number of ways to organize the graph into communities). The result is a tree (dendrogram) of community divisions. Basically a heirarchy of communities.

The only thing that is somewhat discerning (although good to know) is that the contact graphs, at least the sparse ones, are not turning out to be very community oriented.

2008_07_30
I had totally forgotten about this idea I had a while ago to make drums out of PVC piping. I figured I could easily do it by buying pipe that was pre-cut and then just drilling some holes for the lugs and boom, you're done. Anyways, I'm in Urbana, IL at the University of Illinois (UIUC for short). I'm attending the AMAST'08 conference and it's been fairly enlightening. First off, I know I don't want to go into algebraic methodologies for software technology. Although, I see the applications and I suppose it's always good to use. But the whole thing about something like Algebra because it's such a broad math formalism. It is basically using symbols in a mathimatical way that also applies to another area, in this case computer programs. So the conference has ended up being a lot about verification of computer programs which I have to appreciate because I like compilers and a lot of the application from this work is to make compilers that allow me to be more assured what i've programmed is OK. Although, it's just like spell checking. People have possibly become worse spellers _because_ they now have Word or some other special application to correct their bad spelling. But I guess there is another school of thought that might say that people are able to instantly learn to spell better. I know there are a few words I constantly spell bad but eventually I got tired of the spell checker catching them so I decided to learn how to correctly spell them. If there weren't spell checkers then I would have never know. Who would respond to my emails telling me that I had spelled the word incorrectly? Instead they would just think "what an idiot" and go on with their day and I'd be left looking like an idiot. Now there was something else I was enlightened about and as I sat here thinking two seconds I just remembered it was that I believe the internet is killing conferences. Well, not just the internet, but just the evolution of technology. I realize that sitting in a conference listening to nine presentations today allowed me to get a feel for each paper but in this case, the presentations were too detailed to be of benefit to me. Now that I think about it, the real reason I was distracted today was because the essence of the presentations were so detailed and less problem oriented or applied that they just went way over my head. In the end, this meant I couldn't sit there and go through each detail. It was a bunch of algebra on the slides and I had hardly any idea what it meant. Ugh. It does make me feel like an idiot. And now I'm tired and can't write much more. Snooze Factory. But overall the conference has been motivating. I wish I was at home getting more things done instead of being away from home. For me there are times to learn about things but I know I won't remember EVERYTHING about today and thus I'll have to go back and find the proper research again some other time when I truly need to apply it. Unfortunately, I don't need it now.

2008_07_30

I had totally forgotten about this idea I had a while ago to make drums out of PVC piping. I figured I could easily do it by buying pipe that was pre-cut and then just drilling some holes for the lugs and boom, you're done.

Anyways, I'm in Urbana, IL at the University of Illinois (UIUC for short). I'm attending the AMAST'08 conference and it's been fairly enlightening. First off, I know I don't want to go into algebraic methodologies for software technology. Although, I see the applications and I suppose it's always good to use. But the whole thing about something like Algebra because it's such a broad math formalism. It is basically using symbols in a mathimatical way that also applies to another area, in this case computer programs. So the conference has ended up being a lot about verification of computer programs which I have to appreciate because I like compilers and a lot of the application from this work is to make compilers that allow me to be more assured what i've programmed is OK. Although, it's just like spell checking. People have possibly become worse spellers _because_ they now have Word or some other special application to correct their bad spelling. But I guess there is another school of thought that might say that people are able to instantly learn to spell better. I know there are a few words I constantly spell bad but eventually I got tired of the spell checker catching them so I decided to learn how to correctly spell them. If there weren't spell checkers then I would have never know. Who would respond to my emails telling me that I had spelled the word incorrectly? Instead they would just think "what an idiot" and go on with their day and I'd be left looking like an idiot. Now there was something else I was enlightened about and as I sat here thinking two seconds I just remembered it was that I believe the internet is killing conferences. Well, not just the internet, but just the evolution of technology. I realize that sitting in a conference listening to nine presentations today allowed me to get a feel for each paper but in this case, the presentations were too detailed to be of benefit to me.

Now that I think about it, the real reason I was distracted today was because the essence of the presentations were so detailed and less problem oriented or applied that they just went way over my head. In the end, this meant I couldn't sit there and go through each detail. It was a bunch of algebra on the slides and I had hardly any idea what it meant. Ugh. It does make me feel like an idiot.

And now I'm tired and can't write much more. Snooze Factory.

But overall the conference has been motivating. I wish I was at home getting more things done instead of being away from home. For me there are times to learn about things but I know I won't remember EVERYTHING about today and thus I'll have to go back and find the proper research again some other time when I truly need to apply it. Unfortunately, I don't need it now.

2008_07_23
So I've begun reading the book Writing Your Dissertation in Fifteen Minutes a Day and in the book the author suggests that you write at least 15 minutes each day. In an attempt to do so I'm writing this little blog note. Great. As a starting point i'm going to try an write on this blog. Now, in a more personal note. I had to make the decision this summer to _not_ go on tour with the band in favor of staying home and working on my PhD work. Tara just asked me how I felt about that because before everyone had left I said I was happy with the decision and being here now I am still happy with it. Of course, I am going to miss hanging out with my friends and playing music to crowds of people but I am also noticing how ansy I am... Today I spent a mix of diablo 2 and django. One is a game and one is a web framework. Mainly, I am trying to get this site up and running smoothly. To make my life easier. The idea I have is to add a section called the "Library" where I will add papers I've read and allow them to be tagged based on two criteria: what the paper describes, and what the paper applies. The first is whatever the paper's goal is to do. Say a paper is the paper to know on Model Driven Architectures (MDA), then it would have the tag MDA / Model Driven Architecture as a describes tag. However, another paper may apply MDA to a particular domain such as modeling protiens. So the describes tag would be something like "Modeling Protiens" and the applies tag would be "Model Driven Architecture". Whats nice is an easy way to find if a paper which applies a particular technique to a particular domain and for me it makes sense to track what I've read, thus there will be a summary in there. For now I'm just getting everything cleaned up. I also had to upgrade django on my hosting service and also create a development environment on my local machine. It's all up and running. Oh! I also am learning how to use mercurial as an scm so we will see how that goes. So far so good. I just updated something on the original source and have to pull those changes to my development branch and see how easy it is to merge those changes in. I better make a backup. As for PhD stuff, I'm still trying to keep the ball rolling but I'm not sure what exactly I'm doing. I keep reading and there is all this stuff but my brain is just not coming up with new ideas. Well, I have ideas but I just don't have someone to bounce them off or see if they are any good. I need a goddamn filter and that's it. Well, that's all.

2008_07_23

So I've begun reading the book Writing Your Dissertation in Fifteen Minutes a Day and in the book the author suggests that you write at least 15 minutes each day. In an attempt to do so I'm writing this little blog note. Great. As a starting point i'm going to try an write on this blog.

Now, in a more personal note. I had to make the decision this summer to _not_ go on tour with the band in favor of staying home and working on my PhD work. Tara just asked me how I felt about that because before everyone had left I said I was happy with the decision and being here now I am still happy with it. Of course, I am going to miss hanging out with my friends and playing music to crowds of people but I am also noticing how ansy I am...

Today I spent a mix of diablo 2 and django. One is a game and one is a web framework. Mainly, I am trying to get this site up and running smoothly. To make my life easier. The idea I have is to add a section called the "Library" where I will add papers I've read and allow them to be tagged based on two criteria: what the paper describes, and what the paper applies. The first is whatever the paper's goal is to do. Say a paper is *the* paper to know on Model Driven Architectures (MDA), then it would have the tag MDA / Model Driven Architecture as a describes tag. However, another paper may apply MDA to a particular domain such as modeling protiens. So the describes tag would be something like "Modeling Protiens" and the applies tag would be "Model Driven Architecture". Whats nice is an easy way to find if a paper which applies a particular technique to a particular domain and for me it makes sense to track what I've read, thus there will be a summary in there. For now I'm just getting everything cleaned up. I also had to upgrade django on my hosting service and also create a development environment on my local machine. It's all up and running.

Oh! I also am learning how to use mercurial as an scm so we will see how that goes. So far so good. I just updated something on the original source and have to pull those changes to my development branch and see how easy it is to merge those changes in. I better make a backup.

As for PhD stuff, I'm still trying to keep the ball rolling but I'm not sure what exactly I'm doing. I keep reading and there is all this stuff but my brain is just not coming up with new ideas. Well, I have ideas but I just don't have someone to bounce them off or see if they are any good. I need a goddamn filter and that's it. Well, that's all.