Opened 19 months ago
Closed 2 months ago
#24089 closed enhancement (fixed)
Max common neighbors for Graphs
Reported by:  afrancis  Owned by:  ghrajat1433 

Priority:  major  Milestone:  sage8.8 
Component:  graph theory  Keywords:  neighbors, graphs, link prediction, sd90 
Cc:  dcoudert  Merged in:  
Authors:  Amanda Francis, Rajat Mittal  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  f081682 (Commits)  Commit:  f081682b9db13f14e226cd70a0768dd4a133858d 
Dependencies:  Stopgaps: 
Description
Use adjacency matrix to implement maximum common neighbors score for graphs.
Change History (37)
comment:1 Changed 19 months ago by
 Keywords sd90 added
 Priority changed from minor to major
comment:2 Changed 19 months ago by
 Branch set to u/afrancis/max_common_neighbors_for_graphs
comment:3 Changed 19 months ago by
 Commit set to 96bd2b7f4bda8de468a7176bb15c00622b9c94e7
comment:4 Changed 19 months ago by
 Commit changed from 96bd2b7f4bda8de468a7176bb15c00622b9c94e7 to a749b9313f955b0cf1bf91486969d66be0f9ae31
Branch pushed to git repo; I updated commit sha1. New commits:
a749b93  Added to documentation

comment:5 Changed 19 months ago by
comment:6 Changed 19 months ago by
 Commit changed from a749b9313f955b0cf1bf91486969d66be0f9ae31 to 9436b14b27e08b757044161e118490d6f63970e4
Branch pushed to git repo; I updated commit sha1. New commits:
9436b14  Added authorship line

comment:7 Changed 19 months ago by
 Status changed from new to needs_review
comment:8 Changed 19 months ago by
 Status changed from needs_review to 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 2 months ago by
 Cc dcoudert added
 Milestone changed from sage8.1 to sage8.8
 Owner changed from (none) to ghrajat1433
comment:10 Changed 2 months ago by
 Branch changed from u/afrancis/max_common_neighbors_for_graphs to u/ghrajat1433/24089_max_common_neighbors
 Commit 9436b14b27e08b757044161e118490d6f63970e4 deleted
 Milestone changed from sage8.8 to sage8.7
 Reviewers set to David Coudert
comment:11 Changed 2 months ago by
 Commit set to 514a29a2555b8c3e4d9a3cd771ba6d3c4abeff39
Branch pushed to git repo; I updated commit sha1. New commits:
514a29a  Added Neighbors Method

comment:12 Changed 2 months 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 2 months ago by
 Status changed from needs_work to needs_review
comment:14 Changed 2 months ago by
 Commit changed from 514a29a2555b8c3e4d9a3cd771ba6d3c4abeff39 to 4935d5e2bbda1e51382f2bf6831e26bec812b27e
Branch pushed to git repo; I updated commit sha1. New commits:
4935d5e  removed_xtra_space

comment:15 Changed 2 months ago by
 Status changed from needs_review to 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 2 months ago by
 Commit changed from 4935d5e2bbda1e51382f2bf6831e26bec812b27e to 2039233a1141798e812d8fe7c5a7e8471d4b960c
Branch pushed to git repo; I updated commit sha1. New commits:
2039233  changes_as_per_review

comment:17 followup: ↓ 19 Changed 2 months 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 2 months ago by
 Status changed from needs_work to needs_review
comment:19 in reply to: ↑ 17 Changed 2 months 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:20 Changed 2 months ago by
fixed for maximum value
comment:21 Changed 2 months ago by
 Commit changed from 2039233a1141798e812d8fe7c5a7e8471d4b960c to 4b5431f11938fb6d573356a77b0a09b5a02cf0e6
Branch pushed to git repo; I updated commit sha1. New commits:
4b5431f  fixing max value

comment:22 Changed 2 months 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 2 months ago by
 Commit changed from 4b5431f11938fb6d573356a77b0a09b5a02cf0e6 to 4ea2d8c1178dda31d95eeaffa1739d39223bdf79
Branch pushed to git repo; I updated commit sha1. New commits:
4ea2d8c  fixing remaining bugs

comment:24 Changed 2 months ago by
Thanks for the review. I have fixed the remaining documentation bugs.
comment:27 Changed 2 months ago by
 Branch changed from u/ghrajat1433/24089_max_common_neighbors to u/ghrajat1433/24089_common_neighbors
 Commit 4ea2d8c1178dda31d95eeaffa1739d39223bdf79 deleted
comment:28 Changed 2 months ago by
 Commit set to 2a9c447e048e16573ec1705ab676b1d21ef991a6
Branch pushed to git repo; I updated commit sha1. New commits:
comment:29 Changed 2 months ago by
 Commit changed from 2a9c447e048e16573ec1705ab676b1d21ef991a6 to d5cc829d4a3fd45bdba61a86e0e2c966c37614ab
comment:30 Changed 2 months 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 2 months ago by
 Status changed from needs_work to needs_review
comment:32 Changed 2 months 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 2 months ago by
 Milestone changed from sage8.7 to sage8.8
comment:34 Changed 2 months ago by
 Commit changed from d5cc829d4a3fd45bdba61a86e0e2c966c37614ab to f081682b9db13f14e226cd70a0768dd4a133858d
Branch pushed to git repo; I updated commit sha1. New commits:
f081682  improved the code

comment:35 Changed 2 months ago by
Thanks for the review. I have made the changes.
comment:37 Changed 2 months ago by
 Branch changed from u/ghrajat1433/24089_common_neighbors to f081682b9db13f14e226cd70a0768dd4a133858d
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Max common neighbors added to graphs.py