Opened 5 years ago
Closed 4 years ago
#24089 closed enhancement (fixed)
Max common neighbors for Graphs
Reported by:  Amanda Francis  Owned by:  Rajat Mittal 

Priority:  major  Milestone:  sage8.8 
Component:  graph theory  Keywords:  neighbors, graphs, link prediction, sd90 
Cc:  David Coudert  Merged in:  
Authors:  Amanda Francis, Rajat Mittal  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  f081682 (Commits, GitHub, GitLab)  Commit:  f081682b9db13f14e226cd70a0768dd4a133858d 
Dependencies:  Stopgaps: 
Description
Use adjacency matrix to implement maximum common neighbors score for graphs.
Change History (37)
comment:1 Changed 5 years ago by
Keywords:  sd90 added 

Priority:  minor → major 
comment:2 Changed 5 years ago by
Branch:  → u/afrancis/max_common_neighbors_for_graphs 

comment:3 Changed 5 years ago by
Commit:  → 96bd2b7f4bda8de468a7176bb15c00622b9c94e7 

comment:4 Changed 5 years ago by
Commit:  96bd2b7f4bda8de468a7176bb15c00622b9c94e7 → a749b9313f955b0cf1bf91486969d66be0f9ae31 

Branch pushed to git repo; I updated commit sha1. New commits:
a749b93  Added to documentation

comment:5 Changed 5 years ago by
Authors:  → Amanda Francis 

comment:6 Changed 5 years ago by
Commit:  a749b9313f955b0cf1bf91486969d66be0f9ae31 → 9436b14b27e08b757044161e118490d6f63970e4 

Branch pushed to git repo; I updated commit sha1. New commits:
9436b14  Added authorship line

comment:7 Changed 5 years ago by
Status:  new → needs_review 

comment:8 Changed 5 years ago by
Status:  needs_review → needs_work 

Here I have similar comments as for #24094. You can have a look to [doc.sagemath.org/html/en/developer/coding_basics.html].
comment:9 Changed 4 years ago by
Cc:  David Coudert added 

Milestone:  sage8.1 → sage8.8 
Owner:  set to Rajat Mittal 
comment:10 Changed 4 years ago by
Authors:  Amanda Francis → Amanda Francis, Rajat Mittal 

Branch:  u/afrancis/max_common_neighbors_for_graphs → u/ghrajat1433/24089_max_common_neighbors 
Commit:  9436b14b27e08b757044161e118490d6f63970e4 
Milestone:  sage8.8 → sage8.7 
Reviewers:  → David Coudert 
comment:11 Changed 4 years ago by
Commit:  → 514a29a2555b8c3e4d9a3cd771ba6d3c4abeff39 

Branch pushed to git repo; I updated commit sha1. New commits:
514a29a  Added Neighbors Method

comment:12 Changed 4 years ago by
Done a lot of refactoring and improvement in the original author's code , following the pep8 guidelines and also added vertices option to common_neighbors_matrix method.
comment:13 Changed 4 years ago by
Status:  needs_work → needs_review 

comment:14 Changed 4 years ago by
Commit:  514a29a2555b8c3e4d9a3cd771ba6d3c4abeff39 → 4935d5e2bbda1e51382f2bf6831e26bec812b27e 

Branch pushed to git repo; I updated commit sha1. New commits:
4935d5e  removed_xtra_space

comment:15 Changed 4 years ago by
Status:  needs_review → needs_work 

several comments
common_neighbors_matrix
 We could shorten the short description to
Return a matrix of numbers of common neighbors between each pairs.
an then add the explanation about(i, j)
entry
 pep8:
  ``nonedgesonly`` Boolean (default: `True`); if ``true``, assigns +  ``nonedgesonly`` boolean (default: ``True``); if ``True``, assigns
 remove
# add edge
. Not usefulsage: G = Graph([(0,0)],loops=True) # add edges
 same here
sage: G = graphs.CompleteGraph(4) # Check Complete Graph
 you must document at the begining of the method that it is working for simple graphs only, and so that neither loops nor multiple edges are accepted. Then instead of this test, you could use:
 if self.has_loops():  raise ValueError('Unable to compute simple graph common neighbors for graphs with loops') + self._scream_if_not_simple()
 this method is defined in
graph.py
, so self is not directed.
 use
vertices = list(self)
but the documentation of thevertices
parameter says that default inself.vertices()
.
range(0, self.order())
: no need to add 0 >range(self.order())
 we expect the matrix to be symmetric, so
 for v in range(0, self.order()):  for w in range(0, self.order()):  if v == w:  M[v, w] = 0  if nonedgesonly == True:  if A[v, w] > 0:  M[v, w] = 0 + for v in range(self.order()): + M[v, v] = 0 + for w in range(v + 1, self.order()): + if nonedgesonly and A[v, w]: + M[v, w] = M[w, v] = 0
most_common_neighbors
``nonedgesonly``  Boolean (default: `True`); if ``True``,
same as above
nonadajacent
> nonadjacent`
 alignment 80 columns
+ The common neighbors matrix for a fan on 6 vertices counting only nonadjacent vertex pairs ::
 remove
#Check Complete Graph
 document that the method is for simple graphs only and add
self._scream_if_not_simple()
 document that the method is defined for graphs of order
\geq 2
and do raise ValueError('Unable to find node pairs with common neighbors for graphs with less than 2 nodes') + raise ValueError('this method is defined for graphs with at least 2 vertices')
 what is
max(max(M)
?
 The matrix is symmetric, and the current implementation outputs pair (u, v) and (v, u).
comment:16 Changed 4 years ago by
Commit:  4935d5e2bbda1e51382f2bf6831e26bec812b27e → 2039233a1141798e812d8fe7c5a7e8471d4b960c 

Branch pushed to git repo; I updated commit sha1. New commits:
2039233  changes_as_per_review

comment:17 followup: 19 Changed 4 years ago by
what is max(max(M))
Its the maximum value in a 2d matrix.
The matrix is symmetric, and the current implementation outputs pair (u, v) and (v, u).
no it outputed only (u,v) bcoz second loop started from v.
use vertices = list(self) but the documentation of the vertices parameter says that default in self.vertices().
I have now restored self.vertices in the code. (Or should I do other way round including list(self) in documentation as well as code?
All the changes suggested are commited.
New commits:
2039233  changes_as_per_review

New commits:
2039233  changes_as_per_review

comment:18 Changed 4 years ago by
Status:  needs_work → needs_review 

comment:19 Changed 4 years ago by
Replying to ghrajat1433:
what is max(max(M))Its the maximum value in a 2d matrix.
I don't think so
sage: G = graphs.CycleGraph(4) sage: A = G.adjacency_matrix() sage: M = A**2 sage: M [2 0 2 0] [0 2 0 2] [2 0 2 0] [0 2 0 2] sage: M[1, 1] = 3 sage: M [2 0 2 0] [0 3 0 2] [2 0 2 0] [0 2 0 2] sage: max(max(M)) 2 sage: max(M) (2, 0, 2, 0)
max(M)
returns the "maximum" row according some definition, apparently lexicographic.
use for instance max(M.coefficients())
I have now restored self.vertices in the code. (Or should I do other way round including list(self) in documentation as well as code?
it's consistent with `adjacency_matrix, so it's OK.
comment:21 Changed 4 years ago by
Commit:  2039233a1141798e812d8fe7c5a7e8471d4b960c → 4b5431f11938fb6d573356a77b0a09b5a02cf0e6 

Branch pushed to git repo; I updated commit sha1. New commits:
4b5431f  fixing max value

comment:22 Changed 4 years ago by
almost done ;)
for v in range(self.num_verts()):  for w in range(v, self.num_verts()): + for w in range(v + 1, self.num_verts()):
and also, you can do
 ValueError: This method is not known to work on graphs with loops. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow loops using allow_loops(). + ValueError: This method is not known to work on graphs with + multiedges. Perhaps this method can be updated to handle them, but + in the meantime if you want to use it please disallow multiedges + using allow_multiple_edges().
and
 The (`i` , `j`) entry of the matrix gives the number of common + The `(i , j)` entry of the matrix gives the number of common
comment:23 Changed 4 years ago by
Commit:  4b5431f11938fb6d573356a77b0a09b5a02cf0e6 → 4ea2d8c1178dda31d95eeaffa1739d39223bdf79 

Branch pushed to git repo; I updated commit sha1. New commits:
4ea2d8c  fixing remaining bugs

comment:24 Changed 4 years ago by
Thanks for the review. I have fixed the remaining documentation bugs.
comment:27 Changed 4 years ago by
Branch:  u/ghrajat1433/24089_max_common_neighbors → u/ghrajat1433/24089_common_neighbors 

Commit:  4ea2d8c1178dda31d95eeaffa1739d39223bdf79 
comment:28 Changed 4 years ago by
Commit:  → 2a9c447e048e16573ec1705ab676b1d21ef991a6 

Branch pushed to git repo; I updated commit sha1. New commits:
comment:29 Changed 4 years ago by
Commit:  2a9c447e048e16573ec1705ab676b1d21ef991a6 → d5cc829d4a3fd45bdba61a86e0e2c966c37614ab 

comment:30 Changed 4 years ago by
I have merged it with latest release i.e. 8.7 rc0 to avoid any conflicts. Is milestone 8.7 good or I have to make it 8.8 ?
comment:31 Changed 4 years ago by
Status:  needs_work → needs_review 

comment:32 Changed 4 years ago by
The milestone is now 8.8. Version 8.7 has been released. The last develop version is 8.7, and the first beta of 8.8 will be shortly released.
 a better code when
nonedgesonly = False
 for w in range(v + 1, self.order()):  if nonedgesonly and A[v, w]:  M[v, w] = M[w, v] = 0 + if nonedgesonly: + for w in range(v + 1, self.order()): + if A[v, w]: + M[v, w] = M[w, v] = 0
 Add a
.
at the end ofReturn vertex pairs with maximal number of common neighbors
 only 1 empty line before the INPUT block
 Do simple validity test first
 verts = list(self)  M = self.common_neighbors_matrix(vertices=verts, nonedgesonly=nonedgesonly)  if self.num_verts() < 2:  raise ValueError('this method is defined for graphs with at least 2 vertices') + if self.num_verts() < 2: + raise ValueError('this method is defined for graphs with at least 2 vertices') + verts = list(self) + M = self.common_neighbors_matrix(vertices=verts, nonedgesonly=nonedgesonly)
 no need to call twice
M.coefficients()
. Use a variablecoefficients = M.coefficients()
comment:33 Changed 4 years ago by
Milestone:  sage8.7 → sage8.8 

comment:34 Changed 4 years ago by
Commit:  d5cc829d4a3fd45bdba61a86e0e2c966c37614ab → f081682b9db13f14e226cd70a0768dd4a133858d 

Branch pushed to git repo; I updated commit sha1. New commits:
f081682  improved the code

comment:37 Changed 4 years ago by
Branch:  u/ghrajat1433/24089_common_neighbors → f081682b9db13f14e226cd70a0768dd4a133858d 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
Max common neighbors added to graphs.py