finding cliques with packages Graph and RBGL
1
0
Entering edit mode
@bagatti-davide-1946
Last seen 9.7 years ago
An embedded and charset-unspecified text was scrubbed... Name: not available Url: https://stat.ethz.ch/pipermail/bioconductor/attachments/20061215/ d0d79412/attachment.pl
• 1.2k views
ADD COMMENT •
0
Entering edit mode
Li Long ▴ 120
@li-long-1469
Last seen 9.7 years ago
Hi, Could you provide the dataset? Without any further info, it's hard to judge the results, especially the graph changes dynamically. For instance it's possible that at SOME stage, there is no bigger clicks. If you provide a graph that shows the behaviour (that particular graph), we could help further. Thanks Li > Hello everyone, > > I am using packages Graph and RBGL 1.8 with R 2.3.1 for finding cliques in > a > undirected dynamical graph (it changes over time). > What I do: I load data (adjacency matrix for Graph) from database in a > temporal step. > I transform the matrix in a direct graph using ftM2graphNEL, I make some > analysis (like "degree"), then I transform the > direct graph in a undirect graph using "ugraph" to use maxClique to find > all > the cliques in this graph (which now is undirect). > But I found a problem: in some steps the output of maxClique give me only > clique of length one...but it is a graph with density > near at 1! In the step before it gives me one or two cliques of lenght 27 > or > 28 (the node in the graph are 29). > I give you some outputs: > > step "Before": > > $maxCliques > $maxCliques[[1]] > [1] "1" "3" "6" "7" "8" "9" "11" "12" "14" "16" "17" "18" "19" "20" > "21" > [16] "24" "25" "27" "30" "31" "32" "35" "36" "37" "39" "40" "33" "26" > > $maxCliques[[2]] > [1] "1" "3" "6" "7" "8" "9" "11" "12" "14" "16" "17" "18" "19" "20" > "21" > [16] "24" "25" "27" "30" "31" "32" "35" "36" "37" "39" "40" "22" > > the degree (in the undirected graph) of each node is (node are number from > 1 > to 40, but in time some node (e.g. node 2) "dies"): > > 1 3 6 7 8 9 11 12 14 16 17 18 19 20 21 22 24 25 26 27 30 31 32 33 35 > 36 > 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 26 28 28 27 28 28 28 28 27 28 > 28 > 37 39 40 > 28 28 28 > > and in the "next" step the output is the following: > > $maxCliques > [,1] [,2] > [1,] "1" "1" > [2,] "3" "3" > [3,] "6" "6" > [4,] "7" "7" > [5,] "8" "8" > [6,] "9" "9" > [7,] "11" "11" > [8,] "12" "12" > [9,] "14" "14" > [10,] "16" "16" > [11,] "17" "17" > [12,] "18" "18" > [13,] "19" "19" > [14,] "20" "20" > [15,] "21" "21" > [16,] "24" "24" > [17,] "25" "25" > [18,] "26" "26" > [19,] "27" "27" > [20,] "30" "30" > [21,] "31" "31" > [22,] "32" "32" > [23,] "35" "35" > [24,] "36" "36" > [25,] "37" "37" > [26,] "39" "39" > [27,] "40" "40" > [28,] "33" "22" > > The number of node in each cliques in always 1. > > degree: > 1 3 6 7 8 9 11 12 14 16 17 18 19 20 21 22 24 25 26 27 30 31 32 33 35 > 36 > 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 27 28 28 28 28 28 28 28 27 28 > 28 > 37 39 40 > 28 28 28 > > Some ideas? > Thank-you very much. > > Sorry for my english. > > Davide > > [[alternative HTML version deleted]] > > _______________________________________________ > Bioconductor mailing list > Bioconductor at stat.math.ethz.ch > https://stat.ethz.ch/mailman/listinfo/bioconductor > Search the archives: > http://news.gmane.org/gmane.science.biology.informatics.conductor >
ADD COMMENT •
0
Entering edit mode
Hi Li, thanks for your answer. I cannot send you the full dataset, because it is a MySQL database of various MBs of size, but in the file "data.zip" in attach you find four files with the adjacency matrix (NOTE: for a direct graph, so, for example, 40 19 means there is a link between node 40 and node 19) for package "Graph" in four temporal steps (note: these steps are consecutive) where I found what I described in my first e-mail (but it also happens in other intervals). The first file ("network1.txt"), maxclique found cliques of length 19, in the second and third file ("Network2" and "network3") the maximum clique found has length 1. In the fourth file ("network4") length 19. I also send you the plot of some network indicator: network density ("densita.png") number of active node ("numero_agenti_vivi.png") The total step are 500; the adjacency matrices I sent you are relative at steps 429-430-431-432 Thanks in advance Davide 2006/12/18, lilong at isb-sib.ch <lilong at="" isb-sib.ch="">: > > > Hi, > > Could you provide the dataset? Without any further info, it's hard to > judge the results, especially the graph changes dynamically. For instance > it's possible that at SOME stage, there is no bigger clicks. > > If you provide a graph that shows the behaviour (that particular graph), > we could help further. > > Thanks > > Li > > > Hello everyone, > > > > I am using packages Graph and RBGL 1.8 with R 2.3.1 for finding cliques > in > > a > > undirected dynamical graph (it changes over time). > > What I do: I load data (adjacency matrix for Graph) from database in a > > temporal step. > > I transform the matrix in a direct graph using ftM2graphNEL, I make some > > analysis (like "degree"), then I transform the > > direct graph in a undirect graph using "ugraph" to use maxClique to find > > all > > the cliques in this graph (which now is undirect). > > But I found a problem: in some steps the output of maxClique give me > only > > clique of length one...but it is a graph with density > > near at 1! In the step before it gives me one or two cliques of lenght > 27 > > or > > 28 (the node in the graph are 29). > > I give you some outputs: > > > > step "Before": > > > > $maxCliques > > $maxCliques[[1]] > > [1] "1" "3" "6" "7" "8" "9" "11" "12" "14" "16" "17" "18" "19" > "20" > > "21" > > [16] "24" "25" "27" "30" "31" "32" "35" "36" "37" "39" "40" "33" "26" > > > > $maxCliques[[2]] > > [1] "1" "3" "6" "7" "8" "9" "11" "12" "14" "16" "17" "18" "19" > "20" > > "21" > > [16] "24" "25" "27" "30" "31" "32" "35" "36" "37" "39" "40" "22" > > > > the degree (in the undirected graph) of each node is (node are number > from > > 1 > > to 40, but in time some node (e.g. node 2) "dies"): > > > > 1 3 6 7 8 9 11 12 14 16 17 18 19 20 21 22 24 25 26 27 30 31 32 33 > 35 > > 36 > > 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 26 28 28 27 28 28 28 28 27 > 28 > > 28 > > 37 39 40 > > 28 28 28 > > > > and in the "next" step the output is the following: > > > > $maxCliques > > [,1] [,2] > > [1,] "1" "1" > > [2,] "3" "3" > > [3,] "6" "6" > > [4,] "7" "7" > > [5,] "8" "8" > > [6,] "9" "9" > > [7,] "11" "11" > > [8,] "12" "12" > > [9,] "14" "14" > > [10,] "16" "16" > > [11,] "17" "17" > > [12,] "18" "18" > > [13,] "19" "19" > > [14,] "20" "20" > > [15,] "21" "21" > > [16,] "24" "24" > > [17,] "25" "25" > > [18,] "26" "26" > > [19,] "27" "27" > > [20,] "30" "30" > > [21,] "31" "31" > > [22,] "32" "32" > > [23,] "35" "35" > > [24,] "36" "36" > > [25,] "37" "37" > > [26,] "39" "39" > > [27,] "40" "40" > > [28,] "33" "22" > > > > The number of node in each cliques in always 1. > > > > degree: > > 1 3 6 7 8 9 11 12 14 16 17 18 19 20 21 22 24 25 26 27 30 31 32 33 > 35 > > 36 > > 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 27 28 28 28 28 28 28 28 27 > 28 > > 28 > > 37 39 40 > > 28 28 28 > > > > Some ideas? > > Thank-you very much. > > > > Sorry for my english. > > > > Davide > > > > [[alternative HTML version deleted]] > > > > _______________________________________________ > > Bioconductor mailing list > > Bioconductor at stat.math.ethz.ch > > https://stat.ethz.ch/mailman/listinfo/bioconductor > > Search the archives: > > http://news.gmane.org/gmane.science.biology.informatics.conductor > > > >
ADD REPLY •
0
Entering edit mode
Hi, I took a look at the graphs you sent (network{2,3,4}.txt). I think the problem has more to do with output format than with the result. I used "sapply" instead of "lapply" when converting node index to node names, which causes reformatting... Could you please try to modify maxClique in RBGL/R/interfaces.R to use "lapply" instead of "sapply" and look at the result? Let me know if it works. If so, I'll check in the fix. Thanks Li > Hi Li, > > thanks for your answer. > I cannot send you the full dataset, because it is a MySQL database of > various MBs of size, but in the file "data.zip" in attach you find four > files with the adjacency matrix (NOTE: for a direct graph, so, for > example, > 40 19 means there is a link between node 40 and node 19) for package > "Graph" > in four temporal steps (note: these steps are consecutive) where I found > what I described in my first e-mail (but it also happens in other > intervals). > The first file ("network1.txt"), maxclique found cliques of length 19, in > the second and third file ("Network2" and "network3") the maximum clique > found has length 1. In the fourth file ("network4") length 19. > I also send you the plot of some network indicator: > network density ("densita.png") > number of active node ("numero_agenti_vivi.png") > The total step are 500; the adjacency matrices I sent you are relative at > steps 429-430-431-432 > Thanks in advance > > Davide > > > 2006/12/18, lilong at isb-sib.ch <lilong at="" isb-sib.ch="">: >> >> >> Hi, >> >> Could you provide the dataset? Without any further info, it's hard to >> judge the results, especially the graph changes dynamically. For >> instance >> it's possible that at SOME stage, there is no bigger clicks. >> >> If you provide a graph that shows the behaviour (that particular graph), >> we could help further. >> >> Thanks >> >> Li >> >> > Hello everyone, >> > >> > I am using packages Graph and RBGL 1.8 with R 2.3.1 for finding >> cliques >> in >> > a >> > undirected dynamical graph (it changes over time). >> > What I do: I load data (adjacency matrix for Graph) from database in a >> > temporal step. >> > I transform the matrix in a direct graph using ftM2graphNEL, I make >> some >> > analysis (like "degree"), then I transform the >> > direct graph in a undirect graph using "ugraph" to use maxClique to >> find >> > all >> > the cliques in this graph (which now is undirect). >> > But I found a problem: in some steps the output of maxClique give me >> only >> > clique of length one...but it is a graph with density >> > near at 1! In the step before it gives me one or two cliques of lenght >> 27 >> > or >> > 28 (the node in the graph are 29). >> > I give you some outputs: >> > >> > step "Before": >> > >> > $maxCliques >> > $maxCliques[[1]] >> > [1] "1" "3" "6" "7" "8" "9" "11" "12" "14" "16" "17" "18" "19" >> "20" >> > "21" >> > [16] "24" "25" "27" "30" "31" "32" "35" "36" "37" "39" "40" "33" "26" >> > >> > $maxCliques[[2]] >> > [1] "1" "3" "6" "7" "8" "9" "11" "12" "14" "16" "17" "18" "19" >> "20" >> > "21" >> > [16] "24" "25" "27" "30" "31" "32" "35" "36" "37" "39" "40" "22" >> > >> > the degree (in the undirected graph) of each node is (node are number >> from >> > 1 >> > to 40, but in time some node (e.g. node 2) "dies"): >> > >> > 1 3 6 7 8 9 11 12 14 16 17 18 19 20 21 22 24 25 26 27 30 31 32 >> 33 >> 35 >> > 36 >> > 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 26 28 28 27 28 28 28 28 >> 27 >> 28 >> > 28 >> > 37 39 40 >> > 28 28 28 >> > >> > and in the "next" step the output is the following: >> > >> > $maxCliques >> > [,1] [,2] >> > [1,] "1" "1" >> > [2,] "3" "3" >> > [3,] "6" "6" >> > [4,] "7" "7" >> > [5,] "8" "8" >> > [6,] "9" "9" >> > [7,] "11" "11" >> > [8,] "12" "12" >> > [9,] "14" "14" >> > [10,] "16" "16" >> > [11,] "17" "17" >> > [12,] "18" "18" >> > [13,] "19" "19" >> > [14,] "20" "20" >> > [15,] "21" "21" >> > [16,] "24" "24" >> > [17,] "25" "25" >> > [18,] "26" "26" >> > [19,] "27" "27" >> > [20,] "30" "30" >> > [21,] "31" "31" >> > [22,] "32" "32" >> > [23,] "35" "35" >> > [24,] "36" "36" >> > [25,] "37" "37" >> > [26,] "39" "39" >> > [27,] "40" "40" >> > [28,] "33" "22" >> > >> > The number of node in each cliques in always 1. >> > >> > degree: >> > 1 3 6 7 8 9 11 12 14 16 17 18 19 20 21 22 24 25 26 27 30 31 32 >> 33 >> 35 >> > 36 >> > 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 27 28 28 28 28 28 28 28 >> 27 >> 28 >> > 28 >> > 37 39 40 >> > 28 28 28 >> > >> > Some ideas? >> > Thank-you very much. >> > >> > Sorry for my english. >> > >> > Davide >> > >> > [[alternative HTML version deleted]] >> > >> > _______________________________________________ >> > Bioconductor mailing list >> > Bioconductor at stat.math.ethz.ch >> > https://stat.ethz.ch/mailman/listinfo/bioconductor >> > Search the archives: >> > http://news.gmane.org/gmane.science.biology.informatics.conductor >> > >> >> >
ADD REPLY •
0
Entering edit mode
An embedded and charset-unspecified text was scrubbed... Name: not available Url: https://stat.ethz.ch/pipermail/bioconductor/attachments/20061219/ 6851548b/attachment.pl
ADD REPLY •
0
Entering edit mode
Hi, Then try to read the output vertically :) In your example (quoted below), there are two max cliques: each is of size 28, the 28 nodes of each clique are listed in [,1] or [,2]. Li > Hi, > I am sorry, but I cannot find RBGL/R/interfaces.R in the R library > directory >> >> > and in the "next" step the output is the following: >> >> > >> >> > $maxCliques >> >> > [,1] [,2] >> >> > [1,] "1" "1" >> >> > [2,] "3" "3" >> >> > [3,] "6" "6" >> >> > [4,] "7" "7" >> >> > [5,] "8" "8" >> >> > [6,] "9" "9" >> >> > [7,] "11" "11" >> >> > [8,] "12" "12" >> >> > [9,] "14" "14" >> >> > [10,] "16" "16" >> >> > [11,] "17" "17" >> >> > [12,] "18" "18" >> >> > [13,] "19" "19" >> >> > [14,] "20" "20" >> >> > [15,] "21" "21" >> >> > [16,] "24" "24" >> >> > [17,] "25" "25" >> >> > [18,] "26" "26" >> >> > [19,] "27" "27" >> >> > [20,] "30" "30" >> >> > [21,] "31" "31" >> >> > [22,] "32" "32" >> >> > [23,] "35" "35" >> >> > [24,] "36" "36" >> >> > [25,] "37" "37" >> >> > [26,] "39" "39" >> >> > [27,] "40" "40" >> >> > [28,] "33" "22" >> >> > >> >> > The number of node in each cliques in always 1. >> >> > >> >> > degree: >> >> > 1 3 6 7 8 9 11 12 14 16 17 18 19 20 21 22 24 25 26 27 30 31 >> 32 >> >> 33 >> >> 35 >> >> > 36 >> >> > 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 27 28 28 28 28 28 28 >> 28 >> >> 27 >> >> 28 >> >> > 28 >> >> > 37 39 40 >> >> > 28 28 28
ADD REPLY •
0
Entering edit mode
An embedded and charset-unspecified text was scrubbed... Name: not available Url: https://stat.ethz.ch/pipermail/bioconductor/attachments/20061220/ 5642399f/attachment.pl
ADD REPLY •

Login before adding your answer.

Similar Posts
Loading Similar Posts
Traffic: 427 users visited in the last hour
Content Search
Users
Tags
Badges
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6