6
$\begingroup$

I have IP addresses as feature and I would like to know how much two IP addresses are similar to each other to use the difference in an Euclidean distance measure (in order to quantify the similarities of my data points). What tactic can I use for this?

$\endgroup$
7
  • 1
    $\begingroup$ To you what would make two IP addresses similar? $\endgroup$
    – paparazzo
    Nov 9, 2015 at 13:04
  • $\begingroup$ You could use a GeoIP lookup and literally compare the distance on the earth between them.... $\endgroup$
    – Spacedman
    Nov 9, 2015 at 21:25
  • $\begingroup$ @Spacedman That only works for WWW public IP. OP has not even provided that information. $\endgroup$
    – paparazzo
    Nov 9, 2015 at 21:43
  • $\begingroup$ Yes, I was hoping some clarification would be forthcoming, instead of everyone piling in with "answers"... @marcL? $\endgroup$
    – Spacedman
    Nov 9, 2015 at 21:53
  • $\begingroup$ How they are similar in terms of network not based on earth distance. Sorry for the delay $\endgroup$ Nov 10, 2015 at 14:05

7 Answers 7

5
$\begingroup$

If I understood them correctly, both Jeremy and Edmund's (first) solutions are the same, namely, plain euclidean distance in a 4-dimensional space of IP addresses.BTW, I think a very fast alternative to euclidean distance would be to calculate a hamming distance bit-wise.

Edmund's first update would be better than his second. The reason is simple to state: his 2nd update tries to define a distance measure by considering a non-linear function of the coordinates of a 4D vector. That however will most likely destroy the key properties that it needs to satisfy in order to be a metric, namely

  1. Injectivity: $d(IP_1,IP_2)=0 \iff IP_1=IP_2$,
  2. Symmetry: $d(IP_1,IP_2)=d(IP_2,IP_1)$, and
  3. Triangular inequality: $d(IP_1,IP_2)\leq d(IP_1,IP_3)+d(IP_3,IP_2)\,\forall IP_3$.

The latter is key for later interpreting small distances as close points in IP space. One would need a linear (in the coordinates) distance function. However, simple euclidean distance is not enough as you saw.

Physics (well, differential geometry actually) could lead to a nice solution to this problem: define a metric tensor $g$. In plain english, give weights to each pair of coordinates, take each pair difference, square it and multiply it by its weight, and then add those products. Take the square root of that sum and define it as your distance.

For the sake of simplicity, one could start trying with a diagonal metric tensor.

Example: Say you take $g=\begin{pmatrix}1000 &0 &0 &0 \\0 &100&0&0\\0&0&10&0\\0&0&0&1\end{pmatrix}$ $IP_1=(x_1,x_2,x_3,x_4)$ and $IP_2=(y_1,y_2,y_3,y_4)$. Then the square of the distance is given by $$d(IP_1,IP_2)^2=1000*(x_1-y_1)^2+100*(x_2-y_2)^2+\\ \,+10*(x_3-y_3)^2+1*(x_4-y_4)^2$$ For $IP_1=192.168.1.1,\,IP_2=192.168.1.2$ the distance is clearly 1. However, for $192.168.1.1$ and $191.168.1.1$ the distance is $\sqrt{1000}\approx 32$

Eventually you could play around with different weights and set a kind of normalization where you could fix the value of the maximal distance $d(0.0.0.0,FF.FF.FF.FF)$.

Furthermore, this set up allows for more complex descriptions of your data where the relevant distance would contain "cross-products" of coordinates like say $g_{13}*(x_1-y_1)*(x_3-y_3)$.

EDIT: While this would be a better "weighting" method than using those other I addressed, I realize now it is actualy meaningless: As Anony-Mousse and Phillip mention, IP are indeed 32 dimensional. This means in particular that giving the same weight to all bits in say the 2nd group is in general not sound: One bit could be part of the netmask while the other not. See Anony-Mousse answer for additional objections.

$\endgroup$
4
  • $\begingroup$ Very nice. Thanks for critique. I obviously need to brush up on my Linear Algebra. ;-) $\endgroup$
    – Edmund
    Nov 9, 2015 at 21:12
  • $\begingroup$ As I mentioned, eventually one could introduce a more complex "IP space-time" by considering also non-vanishing off-diagonal elements in $g$. This I guess would depend on the problem he wants to solve, i.e., on the data. However, my first guess is that it easily is overkill. At least one should first try with a diagonal form as in the example above. In such case, there wouldn't be any need to dust-off your LA books, ;-) just following the example, which is, btw, like a problem of vectors in 2 dimensions. $\endgroup$
    – MASL
    Nov 9, 2015 at 21:24
  • $\begingroup$ It's not a fourudimensional space. It's a 32 dimensional space. The dot-representation is just easier to remember. $\endgroup$ Nov 9, 2015 at 23:36
  • $\begingroup$ @Anony-Mousse You are right, there is this other way of looking at it, namely bit-wise. What I propose is independent of how one describes the "IP-space, i.e., whether 4 or 32-dimensional. That said, without other info on the OP's problem, it's seems reasonable to distinguish the usual 4 numbers of an IP and say that 191.0.0.0 and 192.0.0.0 differ more than 0.0.0.0 and 0.0.0.1. $\endgroup$
    – MASL
    Nov 10, 2015 at 0:33
4
$\begingroup$

That's a very interesting question. Similarity here should be computed component-wise, but the thing is from a "business logic" perspective, the similarity of the last 3 numbers doesn't matter if the other 3 sets of numbers are not the same. Keeping that in mind, I would probably do something like the following (there is probably a more elegant way of doing it, and I don't have much time to think about it so forgive me if it doesn't answer your question and for the poor formatting).

Assuming IPv4 of the form aaa.bbb.ccc.ddd, I would so something like:

If aaa_1 == aaa_2:
  If bbb_1 == bbb_2:
    If ccc_1 == ccc_2:
        If ddd_1 == ddd_2:
            Dist = 1;
        Else:
            Dist = (3 + distance(ddd_1,ddd_2))/4;
        End if;
    Else:
        Dist = (2 + distance(ccc_1,ccc_2))/4;
    End if;
  Else:
    Dist = (1 + distance(bbb_1,bbb_2))/4;
  End if;
 Else:
  Dist = distance(aaa_1,aaa_2);
  Return 1/Dist;
$\endgroup$
4
  • $\begingroup$ So, if both addresses are the same you code assigns a distance of 1, not zero. Is that a typo or it does this 1 have a special meaning? (You could make it return a zero at that point so as to avoid a NAN at the return at the bottom.) $\endgroup$
    – MASL
    Nov 9, 2015 at 22:48
  • $\begingroup$ An IP is one 32-bit number. $\endgroup$ Nov 9, 2015 at 23:50
  • $\begingroup$ @MASL This is a similarity metric, I should have precised it. 1 means complete similarity here. $\endgroup$ Nov 10, 2015 at 1:16
  • $\begingroup$ Also I am probably abusing the word "metric" here, forgive me for that. $\endgroup$ Nov 10, 2015 at 1:22
3
$\begingroup$

20 years ago, I would have suggested to use the length of the shared prefix as similarity measure.

So you take two IPs. In their 32 bit representation, not the "pretty printed" x.y.z.w form; the real "int" reoresentation your network stack uses. Then XOR them, count the leading zeros, and you get

distance = 32 - leadingZeros(ip1 XOR ip2)

However, we have exhausted the IPv4 namespace long ago. The last 10 years, the few remaining netblock have been more or less "randomly" (at least from a similarity perspective) been distributed. IP ranges have been relocated and so on.

A lomg time ago, people would have told you routing happens on trees, based on their prefix. So If you wanted to read an IP 10.2.3.4 it would go to 10.0.0.0 then 10.2.0.0 then 10.2.3.0. But that was just the theory. If you manually configured your router, that is what you would do. 10.2 isthe second building, 10.2.3. is the third floor router. History. Within networks, IPs are assigned by DHCP, often first-come-first-served. Within intranet, you have mostly switches not routers. And on the global level, the BGP is responsible for taking care of the big mess of todays routing tables.

In other words: use some database like GeoIP to map the IPs to (approximate) coordinates. Best you can do. IP based similarity is mostly useful on a /24 prefix, but a binary yes/no similarity won't make you happy I guess.

$\endgroup$
1
  • $\begingroup$ I hadn't seen your answer before I replied to your comment on mine. I understand now what you meant. Simple di/similarity measures on the IP's won't help one to distinguish any sort of geographical location. Maybe not even any other kind of useful measure of proximity -organizations have IP ranges assigned at ad-hoc, such that make a distance function superfluous/meaningless. $\endgroup$
    – MASL
    Nov 10, 2015 at 0:41
2
$\begingroup$

IP (v4) addresses are a 32-bit integer, which trivially gives you a metric. However, it may not be a particularly useful metric - 10.255.255.255 and 11.0.0.0 are almost certainly significantly more different than 192.168.1.1 and 192.168.1.2.

$\endgroup$
2
  • $\begingroup$ Exact so do you have any idea ? Maybe one of the answers above ? $\endgroup$ Nov 9, 2015 at 12:22
  • 1
    $\begingroup$ What is a good metric depends on the problem you're trying to solve. You could for instance use one of the geoIP services to get a geolocation for every IP address - but we can't tell you whether that's good for you because we don't know what your problem is. $\endgroup$ Nov 9, 2015 at 12:36
2
$\begingroup$

Like someone else mentioned, treating IPs as int automatically gives higher bits higher weights. I've used variance of IPs which is log scaled.

math.log(np.std([IP(ip).int() for ip in ips]))
$\endgroup$
1
$\begingroup$

2nd Update

The below can be improved as it does not consider the hierarchical structure of an IP address. To account for this the elements of the IP vectors can be non-linearly scaled before computing the distance vector and its norm. This gives more weight to the elements higher in the hierarchy.

Mathematica code

Once we have the 4D vectors from the 1st update each element is scaled based on its position $[x^{2}_{1},x^{\frac{3}{2}}_{2},x^{1}_{3},x^{\frac{1}{2}}_{4}]$.

Subtract @@ (MapIndexed[
       Function[{value, index}, 
        value^((5 - First@index)/2)], #] & /@ {ip1, ip2}) // Norm // N
(* 2209.17 *)

There is information lost in collapsing from 4D down to 1D but this can't be helped if you are looking for a 1D distance metric.


1st Update

An IP address is made up of 4 numbers. Takes these as vectors in 4D and calculate the distance between them ( Distance in Euclidean space ).

Mathematica code

(* Make some IP addresses *)
{ip1, ip2} = 
 StringRiffle[#, "."] & /@ 
  Map[ToString, RandomInteger[{1, 255}, {2, 4}], {2}]
(* {"50.229.29.146", "27.167.216.58"} *)

(* Extract 4D vector *)
{ip1, ip2} = Map[FromDigits, StringSplit[#, "."] & /@ {ip1, ip2}, {2}]
(* {{50, 229, 29, 146}, {27, 167, 216, 58}} *)

(* Calculate distance *)
Norm[ip1 - ip2] // N
(* 216.993 *)

Consider an IP address as a 4D vector. Subtract and calculate the norm.

$\endgroup$
7
  • $\begingroup$ Can you explain a bit more? $\endgroup$ Nov 9, 2015 at 12:23
  • $\begingroup$ @marcL , I was on my phone. Check the update. $\endgroup$
    – Edmund
    Nov 9, 2015 at 13:11
  • 1
    $\begingroup$ So you are assuming that Sim("192.168.1.1", "192.168.1.2") == Sim("191.168.1.1", "192.168.1.1")? $\endgroup$ Nov 9, 2015 at 13:53
  • $\begingroup$ Correct. They are equally similar to one another with this measure. But I see the issue here with the hierarchical nature of the IP addresses. Let me think about that. $\endgroup$
    – Edmund
    Nov 9, 2015 at 14:01
  • $\begingroup$ @JérémieClos So I'm thinking that each element of the vector could be non-linearly scaled before computing the norm of the distance vector. This would give more weight to elements higher in the hierarchy. $\endgroup$
    – Edmund
    Nov 9, 2015 at 14:08
1
$\begingroup$

First you need to distinguish private and public addresses (check wikipedia IP_address#Private_addresses).

Private IPs: the best you can do is compute if 2 addresses COULD be on the same network or not, then you need clues from other features to KNOW if it is the case or no.

Public IPs: For geographic distance, you may want to check web services/API that try to map IP and geographical locations (one google search turned this one for instance enter link description here).

Another point which could be interesting is the "organisational distance", from the IP address you can try to identify the owner of the address (the ISP), check ARIN for instance http://whois.arin.net/rest/net/NET-8-8-8-0-1/pft?s=8.8.8.8.

From there you can try to figure out if two addresses belong to the same organisation or not. You will have to find some way to tell if the organisation is an ISP with private customers or a company with their own network. Please be also aware that some organisations have started to resell blocks from their IPV4 addresses to other companies for money with the effect that addresses that used to be in the same organisation/location can now be thousands of miles away in different companies.

I think it would be wise to consider these informations as probabilities only.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.