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: sage-8.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:

Status badges

Description

Use adjacency matrix to implement maximum common neighbors score for graphs.

Change History (37)

comment:1 Changed 5 years ago by Amanda Francis

Keywords: sd90 added
Priority: minormajor

comment:2 Changed 5 years ago by Amanda Francis

Branch: u/afrancis/max_common_neighbors_for_graphs

comment:3 Changed 5 years ago by git

Commit: 96bd2b7f4bda8de468a7176bb15c00622b9c94e7

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

96bd2b7Max common neighbors added to graphs.py

comment:4 Changed 5 years ago by git

Commit: 96bd2b7f4bda8de468a7176bb15c00622b9c94e7a749b9313f955b0cf1bf91486969d66be0f9ae31

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

a749b93Added to documentation

comment:5 Changed 5 years ago by Amanda Francis

Authors: Amanda Francis

comment:6 Changed 5 years ago by git

Commit: a749b9313f955b0cf1bf91486969d66be0f9ae319436b14b27e08b757044161e118490d6f63970e4

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

9436b14Added authorship line

comment:7 Changed 5 years ago by Amanda Francis

Status: newneeds_review

comment:8 Changed 5 years ago by David Coudert

Status: needs_reviewneeds_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 Rajat Mittal

Cc: David Coudert added
Milestone: sage-8.1sage-8.8
Owner: set to Rajat Mittal

comment:10 Changed 4 years ago by Rajat Mittal

Authors: Amanda FrancisAmanda Francis, Rajat Mittal
Branch: u/afrancis/max_common_neighbors_for_graphsu/gh-rajat1433/24089_max_common_neighbors
Commit: 9436b14b27e08b757044161e118490d6f63970e4
Milestone: sage-8.8sage-8.7
Reviewers: David Coudert

comment:11 Changed 4 years ago by git

Commit: 514a29a2555b8c3e4d9a3cd771ba6d3c4abeff39

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

514a29aAdded Neighbors Method

comment:12 Changed 4 years ago by Rajat Mittal

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 Rajat Mittal

Status: needs_workneeds_review

comment:14 Changed 4 years ago by git

Commit: 514a29a2555b8c3e4d9a3cd771ba6d3c4abeff394935d5e2bbda1e51382f2bf6831e26bec812b27e

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

4935d5eremoved_xtra_space

comment:15 Changed 4 years ago by David Coudert

Status: needs_reviewneeds_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 useful
                sage: 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 the vertices parameter says that default in self.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
  • non-adajacent -> non-adjacent`
  • alignment 80 columns
    +        The common neighbors matrix  for a fan on 6 vertices counting only non-adjacent 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 git

Commit: 4935d5e2bbda1e51382f2bf6831e26bec812b27e2039233a1141798e812d8fe7c5a7e8471d4b960c

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

2039233changes_as_per_review

comment:17 Changed 4 years ago by Rajat Mittal

    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:

2039233changes_as_per_review

New commits:

2039233changes_as_per_review

comment:18 Changed 4 years ago by Rajat Mittal

Status: needs_workneeds_review

comment:19 in reply to:  17 Changed 4 years ago by David Coudert

Replying to gh-rajat1433:

    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 4 years ago by Rajat Mittal

fixed for maximum value

comment:21 Changed 4 years ago by git

Commit: 2039233a1141798e812d8fe7c5a7e8471d4b960c4b5431f11938fb6d573356a77b0a09b5a02cf0e6

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

4b5431ffixing max value

comment:22 Changed 4 years ago by David Coudert

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 git

Commit: 4b5431f11938fb6d573356a77b0a09b5a02cf0e64ea2d8c1178dda31d95eeaffa1739d39223bdf79

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

4ea2d8cfixing remaining bugs

comment:24 Changed 4 years ago by Rajat Mittal

Thanks for the review. I have fixed the remaining documentation bugs.

comment:25 Changed 4 years ago by David Coudert

Status: needs_reviewpositive_review

LGTM

comment:26 Changed 4 years ago by Volker Braun

Status: positive_reviewneeds_work

Merge conflict

comment:27 Changed 4 years ago by Rajat Mittal

Branch: u/gh-rajat1433/24089_max_common_neighborsu/gh-rajat1433/24089_common_neighbors
Commit: 4ea2d8c1178dda31d95eeaffa1739d39223bdf79

comment:28 Changed 4 years ago by git

Commit: 2a9c447e048e16573ec1705ab676b1d21ef991a6

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

comment:29 Changed 4 years ago by git

Commit: 2a9c447e048e16573ec1705ab676b1d21ef991a6d5cc829d4a3fd45bdba61a86e0e2c966c37614ab

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

514a29aAdded Neighbors Method
4935d5eremoved_xtra_space
2039233changes_as_per_review
4b5431ffixing max value
4ea2d8cfixing remaining bugs
d5cc829merged with beta 8.7rc0

comment:30 Changed 4 years ago by Rajat Mittal

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 ?

Last edited 4 years ago by Rajat Mittal (previous) (diff)

comment:31 Changed 4 years ago by Rajat Mittal

Status: needs_workneeds_review

comment:32 Changed 4 years ago by David Coudert

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 of Return 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 variable coefficients = M.coefficients()

comment:33 Changed 4 years ago by Rajat Mittal

Milestone: sage-8.7sage-8.8

comment:34 Changed 4 years ago by git

Commit: d5cc829d4a3fd45bdba61a86e0e2c966c37614abf081682b9db13f14e226cd70a0768dd4a133858d

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

f081682improved the code

comment:35 Changed 4 years ago by Rajat Mittal

Thanks for the review. I have made the changes.

comment:36 Changed 4 years ago by David Coudert

Status: needs_reviewpositive_review

LGTM

comment:37 Changed 4 years ago by Volker Braun

Branch: u/gh-rajat1433/24089_common_neighborsf081682b9db13f14e226cd70a0768dd4a133858d
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.